Pagini recente » Cod sursa (job #2936471) | Cod sursa (job #2311047) | Cod sursa (job #931218) | Cod sursa (job #2480875) | Cod sursa (job #1766009)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
int mat[1001][1001],x,poz,n,m,i,y,k;
queue < int > Q;
bool vizitat[100001];
int bfs(int nod)
{
Q.push(nod);
vizitat[nod] = true;
while(!Q.empty())
{
x = Q.front();
poz = mat[x][0];
for(int i = 1; i <= poz; i++)
if(!vizitat[mat[x][i]])
Q.push(mat[x][i]),vizitat[mat[x][i]] = true;
Q.pop();
}
}
int main()
{
f >> n >> m;
for(i = 1; i <= m; i++)
{
f >> x >> y;
poz = ++mat[x][0];
mat[x][poz] = y;
poz = ++mat[y][0];
mat[y][poz] = x;
}
for(i = 1 ; i <= n; i++)
if(!vizitat[i])
bfs(i),k++;
g << k <<" ";
return 0;
}