Cod sursa(job #870077)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 2 februarie 2013 20:14:32
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>

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

int stiva[100002];
int viz[100002],k,nr;

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++;
            stiva[1]=s;
            k=1;
            viz[s]=start[s];
            while(k>0){
                x=stiva[k];
                z=0;
                for(j=viz[x];j!=0;j=t[1][j]){
                    y=t[0][j];
                    if(viz[y]==0){
                        z=j;
                        j=0;
                    }
                }
                if(z!=0){
                    k++;
                    stiva[k]=y;
                    viz[y]=z;
                }
                else{
                    k--;
                }
            }
        }
    }
    printf("%d ",nr);
    fclose(stdin);
    fclose(stdout);
    return 0;
}