Pagini recente » Cod sursa (job #1018298) | Cod sursa (job #2890382) | Cod sursa (job #1652086) | Cod sursa (job #3142771) | Cod sursa (job #1612649)
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int NMAX = 100010;
vector<int> muchii[NMAX];
vector<int>::iterator it;
int n,m;
bitset<NMAX> mark;
queue<int> coada;
void citire()
{
in>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{
in>>x>>y;
muchii[x].push_back(y);
muchii[y].push_back(x);
}
in.close();
}
void bf(int x)
{
coada.push(x);
mark.set(x);
while(!coada.empty())
{
int y = coada.front();
for(it = muchii[y].begin();it<muchii[y].end();it++)
if(!mark.test(*it))
{
coada.push(*it);
mark.set(*it);
}
coada.pop();
}
}
int main()
{
citire();
int nr = 0;
for(int i=1;i<=n;i++)
if(!mark.test(i))
{
bf(i);
nr++;
}
out<<nr<<"\n";
out.close();
return 0;
}