Cod sursa(job #1024864)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 9 noiembrie 2013 11:21:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#define nmax 100000+5
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n, m;
vector<int> u[nmax];
int viz[nmax];
int cnt_conex;

void citire()
{
    int x, y;
    fin >> n >> m;
    FOR(i, 1, m)
    {
        fin >> x >> y;
        u[x].push_back(y);
        u[y].push_back(x);
    }
}

void dfs(int i)
{
    viz[i] = 1;
    if (!u[i].empty())
        FOR(j, 0, u[i].size()-1)
            if (!viz[u[i][j]])
                dfs(u[i][j]);
}

void rezolvare()
{
    FOR(i, 1, n)
        if (!viz[i])
        {
            dfs(i);
            cnt_conex++;
        }
}

void afisare()
{
    fout << cnt_conex << '\n';
}
int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}