Cod sursa(job #326173)

Utilizator vlad_popaVlad Popa vlad_popa Data 24 iunie 2009 10:50:29
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

#define MAXN 100005
#define pb push_back

int N, M;
vector< int > G[MAXN], C;
vector< vector<int> > CTC;
stack< int > S;
int index[MAXN], lowlink[MAXN], inStack[MAXN];
int ind;

void read () {
    int x, y;
    for (scanf ("%d %d", &N, &M); M--; ){
        scanf ("\n%d %d", &x, &y);
        G[x].pb(y);
    }
}

inline int min (int a, int b) {
    return a < b ? a : b;
}

void tarjan (int nod) {
    index[nod] = lowlink[nod] = ++ind;
    S.push(nod); 
    inStack[nod] = 1;
    
    int sz = G[nod].size();
    for (int i = 0; i < sz; ++ i) {
        if (!index[G[nod][i]]) {
            tarjan (G[nod][i]);
            lowlink[nod] = min (lowlink[G[nod][i]], lowlink[nod]);
        }
        else if (inStack[G[nod][i]])
            lowlink[nod] = min (lowlink[G[nod][i]], lowlink[nod]);
    }    
    
    if (lowlink[nod] == index[nod]) {
        C.clear();
        int n;
        do {
            n = S.top();
            S.pop();
            C.pb(n);
            inStack[n] = 0;
        }
        while (nod != n);
        CTC.pb(C);
    }    
}

void solve () {
    for (int i = 1; i <= N; ++ i)
        if (!index[i])
            tarjan(i);
         
    int sz = CTC.size();
    printf ("%d\n", sz);   
    for (int i = 0; i < sz; ++ i){
        int nrNodes = CTC[i].size();
        for (int j = 0; j < nrNodes; ++ j) {
            printf ("%d ", CTC[i][j]);
        }
        printf ("\n");
    }   
}

int main () {
    freopen ("ctc.in", "r", stdin);
    freopen ("ctc.out", "w", stdout);
    
    read (); 
    solve ();
        
    return 0;
}