Cod sursa(job #1098479)

Utilizator gabrielvGabriel Vanca gabrielv Data 4 februarie 2014 20:48:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 100100
#define minim(a,b) ((a<b)?(a):(b))

int N,M,Nrctc;

int TS[NMAX];

bool used[NMAX];

vector < int > G[NMAX],GT[NMAX],CTC[NMAX];

void Read() {

    freopen("ctc.in","r",stdin);

    int x,y;

    scanf("%d%d",&N,&M);
    while(M--) {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}

void TopologicalSorting(int node)
{
    used[node]=true;

    for(vector < int > ::iterator it=G[node].begin();it!=G[node].end();++it)
        if(!used[*it])
            TopologicalSorting(*it);

    TS[++TS[0]] = node;
}

void DFS(int node)
{
    used[node] = false;

    CTC[Nrctc].push_back(node);

    for(vector < int > ::iterator it=GT[node].begin();it!=GT[node].end();++it)
        if(used[*it])
            DFS(*it);
}

void Kosaraju(){

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

    for(int i=N;i;i--)
        if(used[TS[i]])
        {
            Nrctc++ ;
            DFS(TS[i]);
        }

}

void Print() {

    freopen("ctc.out","w",stdout);

    printf("%d\n",Nrctc);

    for(int i=1;i<=Nrctc;++i) {
        for(vector < int > ::iterator it=CTC[i].begin();it!=CTC[i].end();++it)
            printf("%d ",*it);
        printf("\n");
    }
}

int main(){

    Read();
    Kosaraju();
    Print();
    return 0;
}