Pagini recente » Cod sursa (job #3234288) | Cod sursa (job #823696) | Cod sursa (job #2326266) | Cod sursa (job #1613916) | Cod sursa (job #2157311)
#include <iostream>
#include<fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int N, M, nrcomp;
bool viz[100001];
struct nod
{
int x;
nod *next;
};
nod *v[100001];
void add(nod *&cap, int val)
{
nod *p = new nod;
p->x = val;
p->next = cap;
cap = p;
}
void citiregraf()
{
f >> N >> M;
while(M--)
{
int x, y;
f >> x >> y;
add(v[x], y);
add(v[y], x);
}
}
void dfs(int i)
{
viz[i] = 1;
for(nod *p = v[i]; p != NULL; p = p->next)
if(viz[p->x] == 0)
dfs(p->x);
}
void comp_conexe()
{
nrcomp = 0;
for(int i = 1; i <= N; i++)
if(viz[i] == 0)
{
nrcomp++;
dfs(i);
}
}
int main()
{
citiregraf();
comp_conexe();
g << nrcomp;
return 0;
}