Cod sursa(job #575352)

Utilizator chibicitiberiuChibici Tiberiu chibicitiberiu Data 8 aprilie 2011 10:36:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#define LIM 100002

#include <stdio.h>
#include <vector>
using namespace std;

vector<int> Graf[LIM];
vector<int> Trans[LIM];
int PostOrdine[LIM];
bool Vizited[LIM];
int POsize, NrVf;

vector<int> Componente[LIM];
int Csize;

void DFS (int node)
{
    Vizited[node] = true;
    for (int i=0; i < Graf[node].size(); i++)
        if (!Vizited[Graf[node][i]]) DFS(Graf[node][i]);

    PostOrdine[++POsize] = node;
}

void DFST (int node)
{
    Vizited[node] = false;
    Componente[Csize].push_back(node);

    for (int i=0; i < Trans[node].size(); i++)
        if (Vizited[Trans[node][i]]) DFST(Trans[node][i]);
}


int main()
{
    freopen ("ctc.in", "r", stdin);
    freopen ("ctc.out", "w", stdout);

    int M;
    scanf("%d %d\n", &NrVf, &M);

    for (int x,y; M > 0; M--)
    {
        scanf("%d %d\n", &x, &y);
        Graf[x].push_back(y);
        Trans[y].push_back(x);
    }

    for (int i=1; i <= NrVf; i++)
        if (!Vizited[i]) DFS(i);

    for (int i=NrVf; i>0; i--)
        if (Vizited[PostOrdine[i]]) {
            DFST(PostOrdine[i]);
            Csize++;
        }

    printf("%d\n", Csize);
    for (int i=0; i<Csize; i++, printf("\n"))
        for (int j=0; j<Componente[i].size(); j++)
            printf("%d ", Componente[i][j]);

    return 0;
}