Cod sursa(job #204787)

Utilizator moga_florianFlorian MOGA moga_florian Data 26 august 2008 20:57:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
//Aflare componenete conexe cu multimi disjuncte

#include<stdio.h>
#define Nmax 100005

int t[Nmax],p[Nmax];

int tata(int k){
    while(k!=t[k])
        k=t[k];
    return k;    
}

int main(){

    FILE *fin = fopen("dfs.in","r"),
         *fout = fopen("dfs.out","w");
         
    int N,M;
    fscanf(fin,"%d%d",&N,&M);
    
    for(int i=1;i<=N;i++) t[i]=i,p[i]=1;
    
    for(int i=1;i<=M;i++){
        int x,y;
        fscanf(fin,"%d%d",&x,&y);
        
        int t1 = tata(x), t2=tata(y);
        if(t1!=t2){
            
            if(p[t1] > p[t2])
                t[t2]=t1;
            else
            if(p[t1] < p[t2])
                t[t1]=t2;
            else{
                t[t2]=t1;
                p[t1]++;    
            }
                        
        }
            
    }
    
    int cc=0;
    for(int i=1;i<=N;i++)
        if(t[i]==i)
            cc++;
            
    fprintf(fout,"%d\n",cc);
    
    fclose(fin);
    fclose(fout);
    return 0;
        
}