Cod sursa(job #1287939)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 8 decembrie 2014 11:26:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <vector>

using namespace std;
FILE *f=fopen("ctc.in","r");
FILE *g=fopen("ctc.out","w");


vector<int>a[100005],b[100005],r[100005];
vector<int>::iterator it;


int uz[100005],j,c[100005],n,m,mn,i,x,y,rr;
void df(int k)
{
vector<int>::iterator it;
for(it=a[k].begin();it!=a[k].end();++it)
if (uz[*it]==0){
    uz[*it]=1;df(*it);
   ++mn;
   c[mn]=*it;
}
}
void df1(int k){
vector<int>::iterator it;
uz[k]=0;
for(it=b[k].begin();it!=b[k].end();++it)
if (uz[*it]==1){r[rr].push_back(*it);uz[*it]=0;df1(*it);}
}

void recursie ()
{




}

int main(){
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
 fscanf(f,"%d%d",&x,&y);
 a[x].push_back(y);
 b[y].push_back(x);
}
for(i=1;i<=n;i++)
if (uz[i]==0){uz[i]=1;df(i);c[++mn]=i;}
rr=0;



for(i=n;i>=1;i--)
if (uz[c[i]]==1)
{
rr++;
df1(c[i]);
r[rr].push_back(c[i]);
}
fprintf(g,"%d\n",rr);
for(i=1;i<=rr;i++)
{
for(it=r[i].begin();it!=r[i].end();++it)
fprintf(g,"%d ",*it);
fprintf(g,"\n");
}




fclose(g);
return 0;
}