Cod sursa(job #2194400)

Utilizator cip_ionescuCiprian Ionescu cip_ionescu Data 13 aprilie 2018 10:44:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#define MAX_N 100001
#define MAX_M 200001

using namespace std;

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

int n, m, nr, vf[2 * MAX_M], urm[2 * MAX_M], lst[MAX_N], viz[MAX_N];

void adauga(int x, int y)
{
    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void dfs(int x)
{
    viz[x] = true;
    int p = lst[x], y;
    while (p != 0) {
        y = vf[p];
        if (!viz[y]) dfs(y);
        p = urm[p];
    }
}

int main()
{
    int x, y, c;
    fin >> n >> m;
    for (int i = 1 ; i <= m ; i++) {
        fin >> x >> y;
        adauga(x, y);
        adauga(y, x);
    }
    c = 0;
    for (int i = 1 ; i <= n ; i++) if (!viz[i]) c++, dfs(i);
    fout << c;
    return 0;
}