Pagini recente » Cod sursa (job #1192937) | Cod sursa (job #95960) | Cod sursa (job #2463521) | Cod sursa (job #590955) | Cod sursa (job #607771)
Cod sursa(job #607771)
#include <fstream>
using namespace std;
ifstream fi("dfs.in");
ofstream fo("dfs.out");
const int DIM = 100005;
int viz[DIM], N, M, NC;
struct nod { int v; nod *a; } *V[DIM];
void add (int a, int b)
{
nod *q = new nod;
q->v = b;
q->a = V[a];
V[a] = q;
}
void dfs (int n)
{
viz[n] = 1;
int f;
for (nod *q = V[n]; q != NULL; q = q->a)
{
f = q->v;
if (viz[f] == 0)
dfs (f);
}
}
int main ()
{
fi >> N >> M;
for (int i = 1; i <= N; i++)
V[i] = NULL;
for (int i = 0, a, b; i < M; i++)
{
fi >> a >> b;
add (a, b);
add (b, a);
}
for (int i = 1; i <= N; i++)
if (viz[i] == 0)
{
dfs (i);
NC++;
}
fo << NC;
return 0;
}