Cod sursa(job #903283)

Utilizator visanrVisan Radu visanr Data 1 martie 2013 19:43:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

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

int N, M, X, Y, Used[Nmax], TopSort[Nmax], CrtComp[Nmax];
vector<vector<int> > Comp;
vector<int> G[Nmax], GT[Nmax];

void DFS_First(int Node)
{
    Used[Node] = 1;
    for(IT it = G[Node].begin(); it != G[Node].end(); ++it)
        if(!Used[*it])
            DFS_First(*it);
    TopSort[++TopSort[0]] = Node;
}

void DFS_Second(int Node)
{
    Used[Node] = 0;
    for(IT it = GT[Node].begin(); it != GT[Node].end(); ++it)
        if(Used[*it])
            DFS_Second(*it);
    CrtComp[Node] = CrtComp[0];
}

void Kosaraju()
{
    int i, j;
    for(i = 1; i <= N; i++)
        if(!Used[i])
            DFS_First(i);
    reverse(TopSort + 1, TopSort + TopSort[0] + 1);
    for(i = 1; i <= N; i++)
        if(Used[TopSort[i]])
        {
            CrtComp[0] ++;
            DFS_Second(TopSort[i]);
        }
    Comp = vector<vector<int> > (CrtComp[0], vector<int>());
    printf("%i\n", CrtComp[0]);

    for(i = 1; i <= N; i++) Comp[CrtComp[i] - 1].push_back(i);
    for(i = 0; i < CrtComp[0]; printf("\n"), i++)
        for(j = 0; j < Comp[i].size(); j++)
            printf("%i ", Comp[i][j]);
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int i;
    scanf("%i %i", &N, &M);
    for(i = 1; i <= M; i++)
    {
        scanf("%i %i", &X, &Y);
        G[X].push_back(Y);
        GT[Y].push_back(X);
    }
    Kosaraju();
    return 0;
}