Cod sursa(job #662028)

Utilizator proflaurianPanaete Adrian proflaurian Data 15 ianuarie 2012 18:27:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<cstdio>
#include<vector>
#include<bitset>
#define V 100001
using namespace std;
vector<vector<int> > CTC;
vector<int> v[V],S,P,ctc;
bitset<V> U;
int n,m,x,y,Nr[V];
void DF(int);
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--){scanf("%d%d",&x,&y);v[x].push_back(y);}
    for(int i=1;i<=n;i++)if(!Nr[i])DF(i);
    n=CTC.size();printf("%d\n",n);
    for(n--;n>=0;n--)
    {
        for(;CTC[n].size();){printf("%d ",CTC[n].back());CTC[n].pop_back();}
        printf("\n");
        CTC.pop_back();
    }
    return 0;
}
void DF(int nod)
{
    Nr[nod]=++m;S.push_back(nod);P.push_back(nod);
    for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
    {
        if(!Nr[*it]){DF(*it);continue;}
        if(U[*it])continue;
        while(Nr[P.back()]>Nr[*it])P.pop_back();
    }
    if(P.back()!=nod)return;
    ctc.resize(0);
    for(x=-1;x-nod;){x=S.back();U[x]=1;ctc.push_back(x);S.pop_back();}
    CTC.push_back(ctc);
    P.pop_back();
}