Cod sursa(job #1366631)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 1 martie 2015 12:19:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
#include <vector>

#define NN 100008

using namespace std;
vector <int> a[NN],b[NN],r[NN],c;
vector <int>::iterator it;
int use[NN],n,m,i,x,y,nr;

void dfs(int k){
vector <int>::iterator it;
use[k]=1;
for(it=a[k].begin();it!=a[k].end();++it)
if(use[*it]==0){
 dfs(*it);
 c.push_back(*it);
}
}

void dfs1(int k){
vector <int>::iterator it;
use[k]=0;
for(it=b[k].begin();it!=b[k].end();++it)
if (use[*it]==1){
r[nr].push_back(*it);
dfs1(*it);
}


}

int main()
{
freopen("ctc.in", "r",stdin);
freopen("ctc.out", "w",stdout);

scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
a[x].push_back(y);
b[y].push_back(x);
}

for(i=1;i<=n;i++)
if (use[i]==0){dfs(i);c.push_back(i);}

for(i=n-1;i>=0;i--)
if (use[c[i]]==1){nr++;r[nr].push_back(c[i]);dfs1(c[i]);}

printf("%d\n",nr);
for(i=1;i<=nr;i++){
for(it=r[i].begin();it!=r[i].end();++it)
printf("%d ",*it);
printf("\n");
}

return 0;
}