Pagini recente » Cod sursa (job #2836456) | Cod sursa (job #1704726) | Cod sursa (job #1926530) | Cod sursa (job #129691) | Cod sursa (job #3294099)
#include<fstream>
#include<algorithm>
#include<queue>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
int n, m, p, q, M[1000][1000],i,j,V[100000],v[100005];
void bfs(int k)
{
queue<int>Q;
Q.push(k);
V[k] = p;
while (!Q.empty())
{
k = Q.front();
for (int i = 1; i <= n; i++)
{
if (M[i][k] == 1 && V[i] == 0)
{
V[i] = p;
Q.push(i);
}
}
Q.pop();
}
}
int main()
{
int i, j;
cin >> n >> m;
while (m--)
{
cin >> i >> j;
M[i][j] = 1;
M[j][i] = 1;
}
for (int i = 1; i <= n; i++)
{
if (V[i] == 0)
{
++p;
bfs(i);
}
}
cout << p << endl;
}