Cod sursa(job #362801)
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
#define N 100000
vector<int> g[N + 1];
int n, m, c;
queue<int> q;
int d[N + 1];
void citeste()
{
int i, x, y;
scanf("%d%d", &n, &m);
for(i = 1; i <= m; ++i)
{
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
}
void bfs(int s)
{
int e;
d[s] = 1;
q.push(s);
vector<int> :: iterator i;
while(!q.empty())
{
e = q.front();
q.pop();
for(i = g[e].begin(); i != g[e].end(); ++i)
{
if(d[*i] == 0)
{
d[*i] = 1;
q.push(*i);
}
}
}
}
void scrie()
{
printf("%d\n", c);
}
void det_componente()
{
int k;
for(k = 1; k <= n; ++k)
{
if(d[k] == 0)
{
bfs(k);
c++;
}
}
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
citeste();
det_componente();
scrie();
return 0;
}