Pagini recente » Cod sursa (job #491093) | Cod sursa (job #1482696) | Cod sursa (job #2661481) | Cod sursa (job #2437987) | Cod sursa (job #2165796)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct nod
{
int val;
nod *next;
};
nod *v[100001];
int N, M, nrc;
bool viz[100001];
void add_nod(nod *&cap, int x)
{
nod *p = new nod;
p->val = x;
p->next = cap;
cap = p;
}
void DFS(int x)
{
viz[x] = 1;
for(nod *p = v[x]; p != NULL; p = p->next)
if(viz[p->val] == 0)
DFS(p->val);
}
void comp_conexe()
{
nrc = 0;
for(int i = 1; i <= N; i++)
if(viz[i] == 0)
{
nrc++;
DFS(i);
}
}
int main()
{
int x, y;
f >> N >> M;
for(int i = 1; i <= M; i++)
{
f >> x >> y;
add_nod(v[x], y);
add_nod(v[y], x);
}
comp_conexe();
g << nrc;
return 0;
}