Pagini recente » Cod sursa (job #609127) | Cod sursa (job #3259800) | Cod sursa (job #799125) | Cod sursa (job #568659) | Cod sursa (job #719810)
Cod sursa(job #719810)
#include<cstdio>
#include<vector>
#include<queue>
#define _NM 100010
using namespace std;
vector<int> lAd[_NM];
bool viz[_NM];
bool comp_conexa(int s)
{
if (viz[s]) return 0;
queue<int> q;
q.push(s);
while(!q.empty())
{
int cur=q.front();q.pop();
viz[cur]=1;
for (vector<int>::iterator it=lAd[cur].begin();it!=lAd[cur].end();++it)
if (!viz[*it]) q.push(*it);
}
return 1;
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int nN,nM;
scanf("%d%d",&nN,&nM);
for (int i=1;i<=nM;i++)
{
int nod1, nod2;
scanf("%d%d",&nod1,&nod2);
lAd[nod1].push_back(nod2);
lAd[nod2].push_back(nod1);
}
int nr_con=0;
for (int i=1;i<=nN;i++)
if (comp_conexa(i)) nr_con++;
printf("%d",nr_con);
return 0;
}