Cod sursa(job #978216)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 28 iulie 2013 12:31:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int rez, n, m;
bool v[100010];
vector<int> a[100010];

void citire()
{
    int x, y, i;
    scanf("%d%d", &n, &m);
    for(i = 0; i < m; i++)
    {
        scanf("%d%d", &x, &y);
        a[x-1].push_back(y-1);
        a[y-1].push_back(x-1);
    }
}

void neutr(int x)
{
    if(v[x])
        return;
    v[x] = true;
    for(int i = 0; i < a[x].size(); i++)
        neutr(a[x][i]);
}

void solve()
{
    for(int i = 0; i < n; i++)
        if(v[i] == false)
        {
            rez++;
            neutr(i);
        }
}

int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    citire();
    solve();
    printf("%d\n", rez);
    return 0;
}