Cod sursa(job #1815820)

Utilizator TopiAlexTopala Alexandru TopiAlex Data 25 noiembrie 2016 20:05:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <vector>
#define N_MAX 100002
#define M_MAX 200002
using namespace std;

int n, m;
vector<int> lists[N_MAX];
bool viz[N_MAX];

inline void citire();
inline void DFS(int);

int main()
{
    citire();
    int conexe = 0;

    for (int i = 1; i <= n; ++i) {
        if (!viz[i]) {
            DFS(i);
            conexe++;
        }
    }

    printf("%d\n", conexe);
    return 0;
}

inline void citire() {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    scanf("%d%d", &n, &m);

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

inline void DFS(int nod){
    viz[nod] = true;
    int v_size = lists[nod].size();

    for (int i = 0; i < v_size; ++i) {
        if (!viz[lists[nod][i]]) {
            DFS(lists[nod][i]);
        }
    }

}