Cod sursa(job #241316)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 9 ianuarie 2009 20:00:49
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <stdio.h>
#include <vector>
#include <stack>
#define minim(a,b) ((a<b)?a:b)
#define pb(a) push_back(a)
using namespace std;
long n,m,i,j,nod,scc,index=1;
long x[200002],y[200002],g[100002],ind[100002],low[100002],inq[100002];
int * v[100002];
vector <int>sol[100002];
stack <int> Q;

void tarjan(long x){
   long nod;
   ind[x]=low[x]=index;
   inq[x]=1;
   index++;
   Q.push(x);
   for (int i=0;i<g[x];++i){
       nod=v[x][i];
       if (!ind[nod]){
          tarjan(nod);
          low[x]=minim(low[x],low[nod]);
       }
       else if (inq[nod])low[x]=minim(low[x],low[nod]);
   }
   if (ind[x]==low[x]){
      scc++;
      do{
        nod=Q.top();Q.pop();
        sol[scc].pb(nod);
        inq[nod]=0;
      }while (nod!=x);
   }
}
int main(){
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%ld %ld",&n,&m);
    for (i=1;i<=m;++i){scanf("%ld %ld",&x[i],&y[i]);g[x[i]]++;}
    for (i=1;i<=n;i++)v[i]=(int*)malloc(g[i]*sizeof(int)),g[i]=0;
    for (i=1;i<=m;++i)v[x[i]][g[x[i]]++]=y[i];
    //////
    for (i=1;i<=n;++i)if (!ind[i])tarjan(i);
    //////
    printf("%ld\n",scc);
    for (i=1;i<=scc;++i){
        for (j=0;j<sol[i].size();++j)
            printf("%ld ",sol[i][j]);
        printf("\n");
    }
return 0;
}