Cod sursa(job #771629)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 26 iulie 2012 17:26:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <cassert>
#include <cstdio>
#include <stack>
#include <vector>

using namespace std;

const int nmax=100000;

//int n2;
int ind, nsol;

bool in_st[nmax+1];
int idx[nmax+1], ll[nmax+1];
stack <int> st;
vector <int> g[nmax+1], vsol[nmax]; 

void dfs(int x){
    ++ind;
    idx[x]=ind;
    ll[x]=ind;
    st.push(x); in_st[x]=1;

    /*fprintf(stderr, "\n%d...............idx[%d]=%d\n", x, x, ind);
    for (int i=1; i<=n2; ++i){
        fprintf(stderr, "%d ", in_st[i]);
    }*/

    for (vector <int>::iterator it=g[x].begin(); it!=g[x].end(); ++it){
        if (!idx[*it]){
            dfs(*it);
            if (ll[*it]<ll[x]){
                ll[x]=ll[*it];
            }
        }else if (in_st[*it]){
            if (ll[*it]<ll[x]){
                ll[x]=ll[*it];
            }
        }
        /*if (x==8&& (*it==7)){
            fprintf(stderr, "confirmed");
        }*/

    }

    //fprintf(stderr, "\n%d..................ll[%d]=%d\n", x, x, ind);
    if (idx[x]==ll[x]){
        //fprintf(stderr, "\n--->%d\n", x);
        int node;
        do{
            node=st.top();
            st.pop(); in_st[node]=0;
            vsol[nsol].push_back(node);
        }while (x!=node);
        
        ++nsol;
    }
}

int main(){
    int n, m;

    assert(freopen("ctc.in", "r", stdin));
    assert(scanf(" %d %d ", &n, &m));
    //n2=n;
    for (; m; --m){
        int x, y;

        assert(scanf(" %d %d ", &x, &y));
        g[x].push_back(y);
        /*if (x==8&& y==7){
            fprintf(stderr, "conf2");
        }*/
    }

    for (int i=1; i<=n; ++i){
        if (!idx[i]){
            //fprintf(stderr, "%d\n", i);
            dfs(i);
        }
    }

    assert(freopen("ctc.out", "w", stdout));
    printf("%d\n", nsol);
    for (int i=0; i<nsol; ++i){
        for (vector <int>::iterator it=vsol[i].begin(); 
            it!=vsol[i].end(); ++it){

            printf("%d ", *it);
        }
        printf("\n");
    }

    return 0;
}