Cod sursa(job #1740737)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 12 august 2016 11:13:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>

using namespace std;

void DFS1 (unsigned int k);
void DFS2 (unsigned int k);

unsigned int N, M;
unsigned int x, y;

vector <unsigned int> v1[100001], v2[100001];
unsigned int postord[100001];
bool seen[100001];
unsigned int i, j, w;

vector <unsigned int> sol[100001];
unsigned int solution;

int main()
{
    ifstream fin ("ctc.in");
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> x >> y;
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
    for (i=1; i<=N; i++)
        if (!seen[i])
            DFS1(i);
    for (i=N; i>=1; i--)
        if (seen[postord[i]])
        {
            solution++;
            DFS2(postord[i]);
        }
    ofstream fout ("ctc.out");
    fout << solution << '\n';
    for (i=1; i<=solution; i++)
    {
        for (j=0; j<sol[i].size(); j++)
            fout << sol[i][j] << ' ';
        fout << '\n';
    }
    fout.close();
    return 0;
}

void DFS1 (unsigned int k)
{
    unsigned int i;
    seen[k] = 1;
    for (i=0; i<v1[k].size(); i++)
        if (!seen[v1[k][i]])
            DFS1(v1[k][i]);
    postord[++w] = k;
}

void DFS2 (unsigned int k)
{
    unsigned int i;
    seen[k] = 0;
    sol[solution].push_back(k);
    for (i=0; i<v2[k].size(); i++)
        if (seen[v2[k][i]])
            DFS2(v2[k][i]);
}