Cod sursa(job #804724)

Utilizator raluca_vacaruVacaru Raluca-Ioana raluca_vacaru Data 30 octombrie 2012 11:03:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#define MAXN 100001
#define MAXM 200001

using namespace std;

struct node {int inf; node* next;};

int n, m, c;
node* a[MAXN];
int viz[MAXN];

void init () {
    for (int i=1; i<=n; ++i)
        a[i] = NULL;
}

void push (int x, int y) {
    node* p;
    p = new node;
    p->inf = y;
    p->next = a[x];
    a[x] = p;
}

void read () {
    init ();
    freopen ("dfs.in", "r", stdin);
    scanf ("%d%d", &n, &m);
    int i, x, y;
    for (i=1; i<=m; ++i) {
        scanf ("%d%d", &x, &y);
        push (x, y);
        push (y, x);
    }
    fclose (stdin);
}

void DFS (int i) {
    node* p;
    viz[i] = 1;
    for (p=a[i]; p!=NULL; p=p->next)
        if (!viz[p->inf])
            DFS (p->inf);
}

void solve () {
    int i;
    for (i=1; i<=n; ++i)
        if (viz[i] == 0) {
            ++c;
            DFS (i);
        }
    freopen ("dfs.out", "w", stdout);
    printf ("%d\n", c);
    fclose (stdout);
}

int main () {
    read ();
    solve ();
    return 0;
}