Pagini recente » Cod sursa (job #1819724) | Cod sursa (job #275620) | Cod sursa (job #1060388) | Cod sursa (job #961322) | Cod sursa (job #2348102)
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int v[100001];
vector <int> mat[100001];
void addComp (int x, int nr)
{
v[x] = nr;
int i, n = mat[x].size();
for (i = 0; i < n; ++i)
{
if (!v[mat[x][i]])
{
addComp (mat[x][i], nr);
}
}
}
int main()
{
freopen ("bfs.in", "r", stdin);
freopen ("bfs.out", "w", stdout);
int n, m, i, x, y, nr = 0, j;
scanf ("%d%d", &n, &m);
for (i = 0; i < m; ++i)
{
scanf ("%d%d", &x, &y);
mat[x].push_back(y);
mat[y].push_back(x);
}
queue <int> q;
for (i = 1; i <= n; ++i)
{
if (!v[i])
{
//addComp (i, ++nr);
v[i] = ++nr;
q.push(i);
while (!q.empty())
{
x = q.front();
q.pop();
for (j = 0; j < mat[x].size(); ++j)
{
if(!v[mat[x][j]])
{
v[mat[x][j]] = v[x];
q.push(mat[x][j]);
}
}
}
}
}
printf ("%d", nr);
return 0;
}