Cod sursa(job #870222)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 2 februarie 2013 23:41:25
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<stdio.h>

int n,m,start[100002], t[2][400002];
int s,x,y,i,j,z;

int stiva[100002];
int viz[100002],nr;
void dfs(int vf){
    int k,x,y,j,z;
    stiva[1]=s;
    k=1;
    viz[s]=1;
    while(k>0){
        x=stiva[k];
        z=0;
        for(j=start[x];j!=0;j=t[1][j]){
            y=t[0][j];
            if(viz[y]==0){
                z=1;
                j=0;
            }
        }
        if(z!=0){
            k++;
            stiva[k]=y;
            viz[y]=1;
        }
        else{
            k--;
        }
    }
}
int main(){
    freopen("dfs.in","rt",stdin);
    freopen("dfs.out","wt",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++){
        start[i]=0;
        viz[i]=0;
    }
    j=0;
    for (i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        j++;
        t[0][j]=y;
        t[1][j]=start[x];
        start[x]=j;
        j++;
        t[0][j]=x;
        t[1][j]=start[y];
        start[y]=j;
    }
    nr=0;
    for (s=1;s<=n;s++){
        if(viz[s]==0){
            nr++;
            df(s);
        }
    }
    printf("%d ",nr);
    fclose(stdin);
    fclose(stdout);
    return 0;
}