Cod sursa(job #1411882)

Utilizator BaTDucKMocanu George BaTDucK Data 31 martie 2015 23:43:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<bits/stdc++.h>

#define Nmax 100005
#define IT vector < int > :: iterator

using namespace std;

int N, M, Nr_CTC;
vector < int > G[Nmax], G_t[Nmax], St[Nmax], aux;
bool viz[Nmax];

void dfs_G(int Nod)
{
    viz[Nod] = 1;
    for(IT it = G[Nod].begin(); it != G[Nod].end(); ++ it)
        if(!viz[*it])
            dfs_G(*it);
    aux.push_back(Nod);
}

void dfs_G_t(int Nod)
{
    St[Nr_CTC].push_back(Nod);
    viz[Nod] = 0;
    for(IT it = G_t[Nod].begin(); it != G_t[Nod].end(); ++ it)
        if(viz[*it])
            dfs_G_t(*it);
}

void Read()
{
    freopen("ctc.in", "r", stdin);
    scanf("%d%d", &N, &M);
    for( ; M; -- M) {
        int X, Y;
        scanf("%d %d", &X, &Y);
        G[X].push_back(Y);
        G_t[Y].push_back(X);
    }
}

void Write()
{
    freopen("ctc.out", "w", stdout);
    printf("%d\n", Nr_CTC);
    for( ; Nr_CTC; printf("\n"), -- Nr_CTC)
        for(IT it = St[Nr_CTC].begin(); it != St[Nr_CTC].end(); ++ it)
            printf("%d ", *it);
}

void Solve()
{
    for(int i = 1; i <= N; ++ i)
        if(!viz[i])
            dfs_G(i);

    for(IT it = aux.end() - 1; it >= aux.begin(); -- it)
        if(viz[*it])
            Nr_CTC ++, dfs_G_t(*it);
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}