Cod sursa(job #1234296)

Utilizator FayedStratulat Alexandru Fayed Data 27 septembrie 2014 00:58:24
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>
#define NMAX 100001
using namespace std;

int n,m,comp;
bool visited[NMAX];
stack < int > stacks;
vector < int > Graph[NMAX];
vector < int > Reverse_Graph[NMAX];
vector < int > Result[NMAX];

void read(){

    int x,y;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);

        for(register int i = 1; i <= m; ++i){

            scanf("%d%d",&x,&y);
                Graph[x].push_back(y);
                Reverse_Graph[y].push_back(x);
        }
}

void DFS(int node){

    visited[node] = 1;
            stacks.push(node);
                for(vector < int > ::iterator it = Graph[node].begin(); it != Graph[node].end(); ++it)
                    if(!visited[*it])
                        DFS(*it);
}

void DFS_Reverse(int node){

    visited[node] = 1;
    Result[comp].push_back(node);

       for(vector < int > ::iterator it = Reverse_Graph[node].begin(); it != Reverse_Graph[node].end(); ++ it)
            if(!visited[*it])
                DFS_Reverse(*it);
}

void Kosaraju(){

int vertex = 0;

    for(register int i=1;i<=n;++i)

        if(!visited[i])
            DFS(i);
memset(visited,0,sizeof(visited));

    while(!stacks.empty()){

        vertex = stacks.top();
        stacks.pop();
                if(!visited[vertex]){

                  comp++;
                  DFS_Reverse(vertex);
             }
        }
}

void write(){

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

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

int main(){

    read();
    Kosaraju();
    write();

return 0;
}