Pagini recente » Cod sursa (job #65337) | Cod sursa (job #2633656) | Cod sursa (job #706765) | Cod sursa (job #1757146) | Cod sursa (job #381129)
Cod sursa(job #381129)
//Problema: http://infoarena.ro/problema/dfs
#include <stdio.h>
#include <vector>
//Global data
struct TNod
{
long Val;
TNod *Urm;
};
TNod *vf[100001], *sf[100001];
char viz[100001];
long N, M, X, Y, Nr=0;
std::vector< std::vector<long> > Stack;
std::vector<long> Aux;
//Prototypes
void AddInList(int list, int val);
void DFS(long nod, long lvl);
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%ld%ld", &N, &M);
for(long i = 0; i<=M-1; i++)
{
scanf("%ld%ld", &X, &Y);
//AddInList(X-1,Y-1);
AddInList(Y-1,X-1);
}
for(long i = 0; i<=N-1; i++)
{
if(!viz[i])
{
Aux.clear();
Aux.push_back(i+1);
Nr++;
DFS(i,i);
Stack.push_back(Aux);
}
}
printf("%ld\n", Nr);
for(int i = 0; i < Nr; i++)
{
for(int j = 0; j < Stack[i].size(); j++)
printf("%ld ", Stack[i][j]);
printf("\n");
}
return 0;
}
void AddInList(int list, int val)
{
if(vf[list]==NULL)
{
vf[list] = new TNod;
vf[list]->Val = val;
vf[list]->Urm = NULL;
sf[list] = vf[list];
}
else
{
TNod *aux = new TNod;
aux->Val =val;
aux->Urm = NULL;
sf[list]->Urm = aux;
sf[list] = aux;
}
}
void DFS(long nod,long lvl)
{
viz[nod] = 1;
//Aux.push_back(nod);
for(TNod* i = vf[nod]; i!=NULL; i=i->Urm)
{
if(!viz[i->Val])
{
DFS(i->Val, lvl);
Aux.push_back(i->Val+1);
}
}
}