Pagini recente » Cod sursa (job #1924235) | Cod sursa (job #973988) | Cod sursa (job #1722150) | Cod sursa (job #1648328) | Cod sursa (job #160159)
Cod sursa(job #160159)
//dfs - componente conexe
#include <stdio.h>
#define INPUT "dfs.in"
#define OUTPUT "dfs.out"
#define NMAX 100001
#define MMAX 200001
int N, M;
int viz[NMAX], ncomp;
struct nod
{
nod*leg;
int vec;
}*graf[NMAX];
void DF(int src)
{
viz[src] = 1;
nod *p;
for(p = graf[src]; p; p = p->leg)
if(!viz[p->vec]) DF(p->vec);
}
int main()
{
freopen(INPUT, "r", stdin);
freopen(OUTPUT, "w", stdout);
scanf("%d %d", &N, &M);
int i;
for(i = 1; i <= N; ++i) graf[i] = NULL;
for(i = 1; i <= M; ++i)
{
int x, y;
scanf("%d %d", &x, &y);
nod *p = new nod;
p -> vec = y;
p -> leg = graf[x];
graf[x] = p;
p = new nod;
p -> vec = x;
p -> leg = graf[y];
graf[y] = p;
}
for(i = 1; i <= N; ++i)
if(!viz[i])
{
++ncomp;
DF(i);
}
printf("%d\n", ncomp);
return 0;
}