Cod sursa(job #1314679)

Utilizator dica69Alexandru Lincan dica69 Data 12 ianuarie 2015 09:52:05
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define nmax 100001
using namespace std;

FILE *f1= fopen("ctc.in","r"),*f2 = fopen("ctc.out","w");

int use[nmax],n,m,i,u,v,x,s[nmax],k,sol,j;
vector <int> a[nmax],aT[nmax],so[nmax];
//vector <int> ::iterator it;


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

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


int main()
{
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]])
{sol++;
DFS2(s[i]);
}

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

fclose(f1);
fclose(f2);
    return 0;
}

//Challenges are what make life interesting and overcoming them is what makes life meaningful.