Cod sursa(job #932619)

Utilizator gabrielvGabriel Vanca gabrielv Data 29 martie 2013 04:11:13
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

#define NMAX 100100
#define minim(a,b) ((a<b)?(a):(b))

int N,M,Nctc,index;

int Idx[NMAX];
int Llink[NMAX];

bool inStack[NMAX];

vector < int > G[NMAX],CTC[NMAX];
stack < int > Stack;

void Read() {

    freopen("ctc.in","r",stdin);

    int x,y;

    scanf("%d%d",&N,&M);
    while(M--) {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
    }
}

void Tarjan(int nod) {

    Idx[nod]=Llink[nod]=index++;
    Stack.push(nod);
    inStack[nod]=true;

    for(unsigned j=0;j<G[nod].size();++j) {
        int vecin=G[nod][j];
        if(!Idx[vecin]) {
            Tarjan(vecin);
            Llink[nod]=minim(Llink[vecin],Llink[nod]);
        }
        else
            if(inStack[vecin])
                Llink[nod]=minim(Llink[vecin],Llink[nod]);
    }

    if(Idx[nod]==Llink[nod]) {
        Nctc++;
        int STop;
        do {
            STop = Stack.top();
            CTC[Nctc].push_back(STop);
            inStack[STop]=false;
            Stack.pop();
        }while(STop!=nod);
    }
}

void TSFH(){

    for(int i=1;i<=N;i++)
        if(!Idx[i])
            Tarjan(i);
}

void Print() {

    freopen("ctc.out","w",stdout);

    printf("%d\n",Nctc);
    for(int i=1;i<=Nctc;++i) {
        for(unsigned j=0;j<CTC[i].size();++j)
            printf("%d ",CTC[i][j]);
        printf("\n");
    }
}

int main(){

    Read();
    TSFH();
    Print();
    return 0;
}