Cod sursa(job #1426753)

Utilizator ButnaruButnaru George Butnaru Data 30 aprilie 2015 16:08:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <stdio.h>
struct date1{
    int m;
    struct date1*next;
    };
date1 *t[100001],*p;
int x,y,i,n,m,fr[100001],sol=0;
void dfs(int x)
{
    date1 *a;
    fr[x]=1; a=t[x];
    while (a){
        if (fr[a->m]==0) dfs(a->m);
        a=a->next;
    }
}
int main(){
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);
    p=new date1; p->m=x; p->next=t[y]; t[y]=p;
    p=new date1; p->m=y; p->next=t[x]; t[x]=p;
}
for (i=1;i<=n;i++)
    if (fr[i]==0) {dfs(i); sol++;}
printf("%d",sol);
return 0;
}