Cod sursa(job #232703)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 15 decembrie 2008 23:19:52
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
struct Nod {
    int x;
    Nod *next;
};

Nod * a[100005];
int m, x, y, n, nc;
char viz[100005];

int insert(Nod * &u, int val)
{
    Nod * v = new Nod;
    v -> x = val;
    v -> next = u;
    u = v;
}
int dfs(int s)
{
    for(Nod *it = a[s]; it; it = it -> next)
     if (!viz[it->x])
     {
        viz[it->x] = nc;
        dfs(it->x);
     }
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&n, &m);
    for(int i = 1; i <= m; i++)
    {
     scanf("%d %d",&x,&y);
     insert(a[x],y);
     insert(a[y],x);
    }

    for(int i = 1; i <= n; i++)
         if (!viz[i])
          {
              nc++;
              dfs(i);
          }

    printf("%d \n",nc);
    return 0;
}