Cod sursa(job #157893)

Utilizator QbyxEros Lorand Qbyx Data 13 martie 2008 12:48:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>
#define maxn 1000001

struct NOD{int nod; NOD *next;};

int n, m, x, y, ok[maxn], r, i;
NOD *g[maxn];

void dfs(int nod)
{
    ok[nod] = 1;

    NOD *p = g[nod];

    while (p)
    {
       if (!ok[p->nod]) dfs(p->nod);
       p = p->next;
    }
}

int main()
{
    freopen("dfs.in", "rt", stdin);
    freopen("dfs.out", "wt", stdout);

    scanf("%d %d", &n, &m);

    for (i = 1; i <= m; ++i)
    {
	NOD *p = new NOD;

	scanf("%d %d", &x, &y);

	p->nod = y;
	p->next = g[x];
	g[x] = p;

	p = new NOD;

	p->nod = x;
	p->next = g[y];
	g[y] = p;
    }

    for (i = 1; i <= n; ++i)
	if (!ok[i])
	{
	     ++r;
	     dfs(i);
	}

    printf("%d", r);

    return(0);
}