Pagini recente » Cod sursa (job #1676001) | Cod sursa (job #1460480) | Cod sursa (job #2772741) | Cod sursa (job #2561600) | Cod sursa (job #874273)
Cod sursa(job #874273)
#include<cstdio>
#include<vector>
#include<bitset>
using namespace std;
int n,nr,comp=1,c[100000],niv[100000];
long int m;
bitset<100000>viz;
vector<int>v[100000];
vector<int>::iterator it;
void citire(){
freopen("dfs.in","r",stdin);
scanf("%d%d",&n,&m);
for(int a,b,i=1;i<=m;++i){
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
}
void dfs(int p){
int k=1;
c[k]=p;
viz[p]=1;
nr++;
while(k>0){
int y=0;
for(it=v[c[k]].begin(); it<v[c[k]].end(); ++it)
if(!viz[*it]){
y=*it;
c[++k]=*it;
viz[*it]=1;
break;
}
if(!y) k--;
else {
c[++k]=y;
viz[y]=1;
nr++;
}
}
if(nr<n){
comp++;
for(int i=1;i<=n;++i)
if(!viz[i])dfs(i);
}
}
int main(){
citire();
dfs(1);
freopen("dfs.out","w",stdout);
printf("%d",comp+1);
return 0;
}