Cod sursa(job #943530)

Utilizator Paula-ElenaPaula-Elena Margarit Paula-Elena Data 25 aprilie 2013 18:05:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<fstream>
#include<vector>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int MAXN = 200010;
int N, M, x, y, fiu, nod, u, s[MAXN], h1, h2;
bool used[MAXN];
vector <int> G[MAXN], F[MAXN], sol[MAXN];

void DFS_suc(int nod){
    int i;
    used[nod] = 1;
    for(i=0; i<G[nod].size(); ++i)
    {
        y = G[nod][i];
        if(used[y] == 0)
            DFS_suc(y);
    }
    s[++h1] = nod;
}

void DFS_pred(int nod){
    int i;
    used[nod] = 1;
    for(i=0; i<F[nod].size(); ++i)
    {
        y = F[nod][i];
        if(used[y] == 0)
            DFS_pred(y);
    }
    sol[h2].push_back(nod);
}

int main(){
    int i, j;
    fin >> N >> M;
    for(i=0; i<M; ++i){
        fin >> nod >> fiu;
        G[nod].push_back(fiu);
        F[fiu].push_back(nod);
    }

    for(i=1; i<=N; ++i)
        if(!used[i])
            DFS_suc(i);

    for(i=1; i<=N; ++i)
        used[i] = 0;

    for(i=N; i>0; --i)
        if(!used[s[i]]){
            ++h2;
            DFS_pred(s[i]);
        }
    fout << h2 << "\n";
    for(i=1; i<=h2; ++i){
        for(j=0; j<sol[i].size(); ++j)
            fout << sol[i][j] << " ";
            fout << "\n";
    }



    fin.close();
    fout.close();

    return 0;
}