Cod sursa(job #579624)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 12 aprilie 2011 12:22:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <string.h>
#define TR(C, i)\
    for(typeof(C.begin()) i = C.begin(); i != C.end(); i++)
#define pb push_back


using namespace std;

int N, M;
const int nmax = 100010;
vector < vector<int> > C;
vector < int > T;
vector < int > G[nmax];
stack <int> S;
int idx[nmax], indecs, lowlink[nmax],In[nmax];

void read()
{
    freopen ("ctc.in", "r", stdin);
    freopen ("ctc.out", "w", stdout);
    scanf("%d %d", &N, &M);
    int i, a, b;
    for(i = 1; i <= M; i++)
    {
        scanf("%d %d", &a, &b);
        G[a].pb( b );
    }
    memset(idx, -1, sizeof(idx));
}

void solve(int nod)
{
    idx[nod] = lowlink[nod] = indecs;
    S.push(nod), In[nod] = 1;
    indecs++;

    TR(G[nod], it)
        if(idx[*it] == -1)
            solve(*it), lowlink[nod] = min(lowlink[nod], lowlink[*it]);
        else if(In[*it]) lowlink[nod] = min(lowlink[nod], lowlink[*it]);

    if(lowlink[nod] == idx[nod])
    {
        int nxt;
        T.clear();
        do{
            nxt = S.top();
            In[nxt] = 0;
            S.pop();
            T.pb( nxt );
        } while(nxt != nod);

        C.pb( T );
    }
}

void OutPut()
{
    printf("%d\n", C.size());
    TR(C, it)
    {
       TR((*it), i)
            printf("%d ", *i);
        printf("\n");
    }
}

int main()
{
    read();
    int i;
    for(i = 1; i <= N; i++)
        if(idx[i] == -1)
            solve(i);
    OutPut();
    return 0;
}