Cod sursa(job #1216236)

Utilizator DjokValeriu Motroi Djok Data 3 august 2014 20:47:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<algorithm>
using namespace std;

typedef struct lnod {
      int info;
      lnod *next;
}*nod;

int i,n,m,x,y,nr,elem[200010];
nod lda[100005],ldat[100005],rs[100005];
bool viz[100005];

void add(int x,nod &y) {
    nod p=new lnod;
    p->info=x;
    p->next=y;
    y=p;
}

void dfs1(int x) {
  viz[x]=1; elem[++m]=x;
  for(nod p=lda[x];p;p=p->next)
  if(!viz[p->info]) dfs1(p->info),elem[++m]=x;
}

void dfs2(int x) {
   add(x,rs[nr]); viz[x]=0;
   for(nod p=ldat[x];p;p=p->next)
   if(viz[p->info]) viz[p->info]=0,dfs2(p->info);
}

int main()
{
  ifstream cin("ctc.in");
  ofstream cout("ctc.out");

  cin>>n>>m;
  while(m--)
  {
    cin>>x>>y;
    add(y,lda[x]);
    add(x,ldat[y]);
  }

  for(i=1,m=0;i<=n;++i)
  if(!viz[i]) dfs1(i);

  for(i=m,nr=0;i>0;--i)
  if(viz[elem[i]]) ++nr,dfs2(elem[i]);

  cout<<nr<<'\n';
  for(i=1;i<=nr;++i)
  {
    for(nod p=rs[i];p;p=p->next) cout<<p->info<<' ';
    cout<<'\n';
  }

 return 0;   
}