Pagini recente » Cod sursa (job #1038949) | Cod sursa (job #1038900) | Cod sursa (job #3331318) | Cod sursa (job #123651) | Cod sursa (job #1073324)
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
vector <int> drum[200001];
deque <int> coada;
int val[100001] = {0};
int n,m,k = 0;
ifstream f("dfs.in");
ofstream g("dfs.out");
void bfs(int start)
{
coada.push_back(start);
while (!coada.empty())
{
int nod = coada.front();
for (int i=0; i<drum[nod].size(); ++i)
{
int t = drum[nod][i];
if (val[t] == 0)
{ val[t] = 1;
coada.push_back(t);
}
}
coada.pop_front();
}
}
int main()
{
f >> n >> m;
for (int i=0;i<m;i++)
{
int x,y;
f >> x >> y;
drum[x].push_back(y);
drum[y].push_back(x);
}
for (int i=1;i<=n;i++)
{
if (val[i] == 0) { k++; bfs(i); };
}
g << k << endl;
return 0;
}