Cod sursa(job #1487912)

Utilizator SmarandaMaria Pandele Smaranda Data 17 septembrie 2015 16:56:55
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

const int N = 100002;

vector <int> graph [N], graph2 [N], CTC [N];
stack <int> st;
bool used [N];
int ctc [N], ob;

void dfs (int x) {
    vector <int> :: iterator it;

    used [x] = 1;
    for (it = graph [x].begin (); it != graph [x].end (); ++ it)
        if (!used [*it])
            dfs (*it);
    st.push (x);
}

void dfs2 (int x) {
    vector <int> :: iterator it;

    ctc [x] = ob;
    CTC [ob].push_back (x);
    for (it = graph2 [x].begin (); it != graph2 [x].end (); ++ it)
        if (!ctc [*it])
            dfs2 (*it);
}

int main () {
    int i, n, a, b, m;
    vector <int> :: iterator it;

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

    scanf ("%d%d", &n, &m);
    for (i = 1; i <= m; i ++) {
        scanf ("%d%d", &a, &b);
        graph [a].push_back (b);
        graph2 [b].push_back (a);
    }
    for (i = 1; i <= n; i ++)
        if (!used [i])
            dfs (i);
    ob = 0;
    while (!st.empty ()) {
        i = st.top ();
        st.pop ();
        if (!ctc [i]) {
            ++ ob;
            dfs2 (i);
        }
    }
    printf ("%d\n", ob);
    for (i = 1; i <= ob; i ++) {
        for (it = CTC [i].begin (); it != CTC [i].end (); ++ it)
            printf ("%d ", *it);
        printf ("\n");
    }
    return 0;
}