Cod sursa(job #874273)

Utilizator MIonutMistreanu Ionut MIonut Data 8 februarie 2013 01:20:42
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#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;
}