Cod sursa(job #1604773)

Utilizator andreitulusAndrei andreitulus Data 18 februarie 2016 16:15:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<stdio.h>
#define nmax 100003
using namespace std;

struct nod{int inf; nod *urm;};

nod *L[nmax], *R[nmax];

int n, m, v[nmax];

void add(int sr, int val)
{
    nod *q;
    q = new nod;
    q->inf = val;
    q->urm = NULL;

    if(L[sr] == NULL)
        L[sr] = R[sr] = q;
    else
        {
            R[sr]->urm = q;
            R[sr] = q;
        }
}



void read()
{
    int i, n1, n2;

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

    for(i = 1; i <= m; i++)
    {
        scanf("%d %d", &n1, &n2);

        add(n1, n2);

        add(n2, n1);
    }
}



void DFS(int r)
{
    nod *q;

    v[r] = 1;

    for(q = L[r]; q != NULL; q = q->urm)
        if(v[q->inf] == 0)
            DFS(q->inf);
}



void solve()
{
    int i, nr = 0;

    for(i = 1; i <= n; i++)
        if(v[i] == 0)
        {
            nr++;
            DFS(i);
        }

    printf("%d", nr);
}




int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    read();

    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}