Cod sursa(job #1061761)

Utilizator RarRaresNedelcu Rares RarRares Data 20 decembrie 2013 11:37:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <cstdio>
#include <vector>
#define nmax 100005


using namespace std;

int n, m;
vector<int> graf[nmax];
bool viz[nmax];
int cc; /**nr de componente conexe*/

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


void adancime(int k)
{
    viz[k] = true;
    vector<int>::iterator it;
    for(it = graf[k].begin(); it != graf[k].end(); ++it)
        if(!viz[*it])
        {
            adancime(*it);
        }
}


void calcul()
{
    for(int i = 1; i <= n; i++)
    if(!viz[i])
    {
        adancime(i);
        cc++;
    }
}
int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    citire();

    calcul();

    cout << cc;
    return 0;
}