Cod sursa(job #1844116)

Utilizator alinp25Alin Pisica alinp25 Data 9 ianuarie 2017 19:08:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
#include <iostream>

#define NMax 100000
#define MMax (NMax * (NMax - 1) / 2)


void read(int &n, std::vector < int > v[]) {
    int k, x, y;
    std::ifstream fin("dfs.in");
    fin >> n >> k;
    for (int i = 0; i < k; i++) {
        fin >> x >> y;
        v[x - 1].push_back(y - 1);
        v[y - 1].push_back(x - 1);
    }
    fin.close();
}


void DFS(int n, std::vector < int > v[], int c[], int x, int nrCnt) {
    c[x] = nrCnt;
    for (int i = 0; i < v[x].size(); i++) {
        if (c[v[x][i]] == 0) {
            DFS(n, v, c, v[x][i], nrCnt);
        }
    }
}


void solve(int n, std::vector < int > v[], int c[], int &nrCnt) {
    for (int i = 0; i < n; i++) {
        if (!c[i]) {
            nrCnt++;
            DFS(n, v, c, i, nrCnt);
        }
    }
}


int main(int argc, char *argv[]) {
    int n, c[NMax] = { 0 }, nrCnt = 0;
    std::vector < int > v[NMax];
    read(n, v);
    solve(n, v, c, nrCnt);
    std::ofstream fout("dfs.out");
    fout << nrCnt;
    fout.close();
    return 0;
}