Cod sursa(job #185785)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 26 aprilie 2008 00:34:48
Problema Parcurgere DFS - componente conexe Scor 35
Compilator c Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#include <stdlib.h>
#define N 100010
int *a[N],n,m;
int cati[N];
int vizitat[N];
void dfs(int x){
     int i;
     vizitat[x]=1;
     for (i=1;i<=cati[x];++i)
         if (!vizitat[a[x][i]])
            dfs(a[x][i]);
}
int main(){
    int x,y,i,r=0;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        ++cati[x];
        ++cati[y];
    }
    fclose(stdin);      
    for (i=1;i<=n;++i){
        a[i]=(int*)malloc(cati[i]+5);
        //a[i]=new int[cati[i]+1];
        cati[i]=0;
    }
    freopen("dfs.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        ++cati[x];
        a[x][cati[x]]=y;
        ++cati[y];
        a[y][cati[y]]=x;
    }
    for (i=1;i<=n;++i)
        if (!vizitat[i]){
           dfs(i);
           ++r;
        }
    printf("%d\n",r);
    return 0;
}