Cod sursa(job #2203592)

Utilizator Menage_a_011UPB Cheseli Neatu Popescu Menage_a_011 Data 12 mai 2018 18:24:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
// https://goo.gl/fBmFxu
#include <bits/stdc++.h>
using namespace std;

#define NMAX        100009
#define MMAX        200009
#define kInf        (1 << 30)
#define kInfLL      (1LL << 60)
#define kMod        666013
#define edge pair<int, int>
#define x first
#define y second

#define USE_FILES "MLC"

#ifdef USE_FILES
#define cin fin
#define cout fout
ifstream fin("dfs.in");
ofstream fout("dfs.out");
#endif

// number of tests from "in"
int test_cnt = 1;
void clean_test();

// your global variables are here
int n, m;
vector<int> G[NMAX];
bitset<NMAX> visited;
int sol;

void dfs(int node) {
    visited[node] = 1;

    for (auto &x : G[node]) {
        if (!visited[x]) {
            dfs(x);
        }
    }
}
// your solution is here
void solve() {
    cin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    sol = 0;
    visited.reset(); // reset all
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            ++sol;
            dfs(i);
        }
    }

    cout << sol << "\n";

    if (test_cnt > 0) {
        clean_test();
    }
}


void clean_test() {
    // clean if needed
    visited.reset(); // reset all

    for (int i = 1; i <= n; ++i) {
        if (G[i].size())  {
            G[i].clear();
        }
    }

    // clean every shit
    n = m = sol = 0;
}

int main() {
    //    cin >> test_cnt;
    while (test_cnt--) {
        solve();
    }

    return 0;
}