Cod sursa(job #1223466)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 28 august 2014 11:28:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>

using namespace std;

int n, m, nrC;

vector<int> vec[100003];

int vizitat[100003];

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

void dfs(int x)
{
    if (vizitat[x])
        return;
    vizitat[x] = 1;
    for (int i = 0; i < vec[x].size(); i++)
        dfs(vec[x][i]);
}

void componenteConexe()
{
    for (int i = 1; i <= n; i++)
    {
        if (!vizitat[i])
        {
            dfs(i);
            nrC++;
        }
    }
}

void afisare()
{
    printf("%d", nrC);
   /* for (int i = 0; i < nrC; i++)
    {
        for (int j = 0; j < componente[i].size(); j++)
            cout << componente[i][j] << " ";
        cout << "\n";
    }*/

}

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