Cod sursa(job #585561)

Utilizator drywaterLazar Vlad drywater Data 30 aprilie 2011 01:42:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>
int n,m;
struct nod{int val; nod *next;};
nod *G[100010];
int i,x,y,nrc,luat[100010];
int add(int a, int b)
{
    nod *nou=new nod;
    nou->val=b;
    nou->next=G[a];
    G[a]=nou;
    return 0;
}
int dfs(int x)
{
    nod *nou=new nod;
    nou=G[x];
    while (nou)
    {
        if (luat[nou->val]) {nou=nou->next; continue;}
        luat[nou->val]=1;
        dfs(nou->val);
        nou=nou->next;
    }
    return 0;
}
int main(void)
{
    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);
        add(x,y);
        add(y,x);
    }
    for (i=1;i<=n;i++)
    {
        if (!luat[i])
            {luat[i]=1; dfs(i); nrc++;}
    }
    printf("%d\n",nrc);
    return 0;
}