Cod sursa(job #1314710)

Utilizator dica69Alexandru Lincan dica69 Data 12 ianuarie 2015 10:32:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define nmax 100010

using namespace std;

vector <int> a[nmax],aT[nmax],sol[nmax];
FILE *f1,*f2;
int n,m,u,v,i,j,s[nmax],k,nr;
int use[nmax];


void DFS(int nod)
{int i;
use[nod]=1;
for (i=0;i<(int)a[nod].size();i++)
if (!use[a[nod][i]]) DFS(a[nod][i]);
s[++k]=nod;
}

void DFS2(int nod)
{int i;
use[nod]=1;
sol[nr].push_back(nod);
for (i=0;i<(int)aT[nod].size();i++)
if (!use[aT[nod][i]]) DFS2(aT[nod][i]);
}

int main()
{f1 = fopen("ctc.in","r");
f2 = fopen("ctc.out","w");
fscanf(f1,"%d%d",&n,&m);
for (i=1;i<=m;i++) {fscanf(f1,"%d%d",&u,&v);a[u].push_back(v);aT[v].push_back(u);}

for (i=1;i<=n;i++)
if (!use[i]) DFS(i);
memset(use,0,sizeof(use));
for (i=n;i>=1;i--)
if (!use[s[i]])
{nr++;
DFS2(s[i]);
}

fprintf(f2,"%d\n",nr);
for (i=1;i<=nr;i++)
{for (j=0;j<(int)sol[i].size();j++) fprintf(f2,"%d ",sol[i][j]);
fprintf(f2,"\n");
}

fclose(f1);
fclose(f2);
}