Cod sursa(job #1922782)

Utilizator RaTonAndrei Raton RaTon Data 10 martie 2017 18:53:39
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> A[100001];
vector <int> AT[100001];
int N;
int C[100001],V[100001], VT[100001];

int df1(int x){
    vector <int> :: iterator it;
    V[x] = 1;
    for( it = A[x].begin(); it != A[x].end();it++ )
        if( V[*it] == 0 )
            df1(*it);
}
int df2(int x){
    vector <int> :: iterator it;
    VT[x] = 1;
    for( it = AT[x].begin(); it != AT[x].end();it++ )
        if( VT[*it] == 0 )
            df2(*it);
}

int main()
{
    int m, i, x, y, j, nrt;
    f >> N;
    f >> m;
    for(i = 1; i <= m; i++){
        f >> x >> y;
        A[x].push_back(y);
        AT[y].push_back(x);
    }
    nrt = 0;
    for( i = 1; i <= N; i++ ){
        if(C[i] == 0){
            nrt++;
            for(j = 1; j <= N; j++)
                V[j] = VT[j] = 0;
            df1(i);
            df2(i);
            for(j = 1; j <= N; j++)
                if(V[j] == 1 && VT[j] == 1)
                    C[j] = nrt;
        }
    }
    g << nrt << '\n';
    for(i = 1; i <= nrt;i++){
        for(j = 1; j <= N; j++)
            if(C[j] == i)
                g << j << " ";
        g << '\n';
    }
    return 0;
}