Pagini recente » Cod sursa (job #2300309) | Cod sursa (job #1019611) | Cod sursa (job #2652760) | Cod sursa (job #2399363) | Cod sursa (job #472850)
Cod sursa(job #472850)
// Parcurgere DFS - componente conexe.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include "stdio.h"
FILE *f=fopen("dfs.in", "r");
FILE *g=fopen("dfs.out", "w");
int n, m, nr;
int viz[100001];
typedef struct nod
{
int x;
struct nod *adr;
};
nod *l[100001];
void add(int dest, int x)
{
nod *p=new nod;
p->x=x;
p->adr=l[dest];
l[dest]=p;
}
void read()
{
fscanf(f, "%d%d", &n, &m);
for (int i=1; i<=m; ++i)
{
int x, y;
fscanf(f, "%d%d", &x, &y);
add(x, y);
add(y, x);
}
}
void dfs(int x)
{
viz[0]++;
viz[x]=1;
if (l[x]==NULL) return;
if (!viz[l[x]->x]) dfs(l[x]->x);
for (nod *p=l[x]; p->adr!=NULL; p=p->adr)
if(!viz[p->adr->x]) dfs(p->adr->x);
}
void program()
{
for (int i=1; i<=n; ++i)
{
if (!viz[i])
{
nr++;
dfs(i);
}
}
fprintf(g, "%d", nr);
}
int main()
{
read();
program();
return 0;
}