Cod sursa(job #605269)

Utilizator cont_de_testeCont Teste cont_de_teste Data 27 iulie 2011 15:04:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
# include <algorithm>
# include <cstdio>
# include <cstring>
# include <vector>
using namespace std;

const char *FIN = "ctc.in", *FOU = "ctc.out";
const int MAX = 100005;

vector <int> G[MAX], Gt[MAX], Gs[MAX], sol;
int N, M, solution, viz[MAX];

void dfp (int P) {
    viz[P] = 1;
    for (vector <int> :: iterator it = G[P].begin (); it != G[P].end (); ++it)
        if (viz[*it] == 0)
            dfp (*it);
    sol.push_back (P);
}

void dfm (int P, int cat) {
    viz[P] = cat;
    for (vector <int> :: iterator it = Gt[P].begin (); it != Gt[P].end (); ++it)
        if (viz[*it] == -1)
            dfm (*it, cat);
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d %d", &N, &M);
    for (int i = 1, x, y; i <= M; ++i) {
        scanf ("%d %d", &x, &y);
        G[x].push_back (y);
        Gt[y].push_back (x);
    }
    for (int i = 1; i <= N; ++i)
        if (viz[i] == 0)
            dfp (i);
    memset (viz, -1, sizeof (viz));
    for (solution = 0; sol.size (); sol.pop_back ())
        if (viz[sol.back ()] == -1)
            dfm (sol.back (), solution++);
    for (int i = 1; i <= N; ++i)
        Gs[viz[i]].push_back (i);

    freopen (FOU, "w", stdout);
    printf ("%d\n", solution);
    for (int i = 0; i < solution; ++i, printf ("\n"))
        for (vector <int> :: iterator it = Gs[i].begin (); it != Gs[i].end (); ++it)
            printf ("%d ", *it);
}