Pagini recente » Cod sursa (job #3133450) | Cod sursa (job #27092) | Cod sursa (job #1543100) | Cod sursa (job #1858850) | Cod sursa (job #3259596)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dfs.in");
ofstream gout("dfs.out");
int n,m;
bool viz[100001];
vector<int>a[100001];
void citire()
{
int x,y;
fin>>n>>m;
while(m--)
{
fin>>x>>y;
a[x-1].push_back(y-1);
a[y-1].push_back(x-1);
}
}
void BFS(int nod)
{
int crt;
queue<int>q;
q.push(nod);
viz[nod]=1;
while(!q.empty())
{
crt=q.front();
for(int i=0; i<a[crt].size(); ++i)
if(!viz[a[crt][i]])
{
viz[a[crt][i]]=1;
q.push(a[crt][i]);
}
q.pop();
}
}
int main()
{
citire();
int comp=0;
for(int l=0; l<n; ++l)if(!viz[l])
{
++comp;
BFS(l);
}
gout<<comp;
return 0;
}