Cod sursa(job #632104)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 10 noiembrie 2011 12:31:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#define N 100003

using namespace std;

int n, m, viz[N], nr;

struct nod
{
    int x;
    nod *urm;
} *a[N];

void add(nod *&p, int x)
{
    nod *q = new nod;
    q -> x = x;
    q -> urm = p;
    p = q;
}

void citire()
{
    scanf ("%d %d ", &n, &m);
    for (int i = 1; i <= m; ++ i)
    {
        int x, y;
        scanf ("%d %d ", &x, &y);
        if (x != y)
        {
            add (a[x], y);
            add (a[y], x);
        }
    }
}

void dfs(int vf)
{
    for (nod *i = a[vf]; i; i = i -> urm)
        if (!viz[i -> x])
        {
            viz[i -> x] = nr;
            dfs (i -> x);
        }
}

void adancime()
{
    for (int i = 1; i <= n; ++ i)
        if (!viz[i])
        {
            viz[i] = (++ nr);
            dfs (i);
        }
    printf ("%d\n", nr);
}

int main()
{
    freopen ("dfs.in", "r", stdin);
    freopen ("dfs.out", "w", stdout);
    citire();
    adancime();
    return 0;
}