Pagini recente » Cod sursa (job #728891) | Cod sursa (job #3201198) | Cod sursa (job #2872207) | Cod sursa (job #1860400) | Cod sursa (job #2351810)
#include <fstream>
#include <vector>
#include <queue>
#define len 100010
#define pb push_back
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
vector<unsigned> v[len];
queue<unsigned> q;
unsigned N, M, count;
bool viz[len];
void bfs(unsigned nod)
{
q.push(nod);
viz[nod] = true;
while(!q.empty())
{
for(unsigned k = 0; k < v[q.front()].size(); ++k)
if(!viz[v[q.front()][k]])
{
viz[v[q.front()][k]] = true;
q.push(v[q.front()][k]);
}
q.pop();
}
}
int main()
{
in >> N >> M;
for(unsigned i = 1; i <= M; ++i)
{
unsigned x, y;
in >> x >> y;
v[x].pb(y);
v[y].pb(x);
}
for(unsigned i = 1; i <= N; ++i)
if(!viz[i])
{
++count;
bfs(i);
}
out << count;
return 0;
}