Cod sursa(job #591815)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 25 mai 2011 17:37:04
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector <long> G[100005];
long N, NCC;
char V[100005];

void Read()
{
    freopen ("dfs.in", "r", stdin);
    long i, X, Y, M;
    scanf ("%ld%ld", &N, &M);
    for (i=0; i<M; i++)
    {
        scanf ("%ld%ld", &X, &Y);
        G[X].push_back(Y);
        G[Y].push_back(X);
    }
}

void Type ()
{
    freopen ("dfs.out", "w", stdout);
    printf ("%ld\n", NCC);
}

void DFS (long X)
{
    long i, n;
    V[X]=1;
    n=G[X].size();
    for (i=0; i<n; i++)
    {
        if (V[G[X][i]]==0)
        {
            DFS (G[X][i]);
        }
    }
}

int main()
{
    long i;
    Read ();
    for (i=0; i<N; i++)
    {
        if (V[i]==0)
        {
            DFS(i);
            NCC++;
        }
    }
    Type ();
    return 0;
}