Cod sursa(job #1845950)

Utilizator msciSergiu Marin msci Data 11 ianuarie 2017 23:46:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <bits/stdc++.h>
using namespace std;
#define rep(i, from, to) for (int i = (from); i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename T> void _dbg(const char *sdbg, T h) { cerr << sdbg << " = " << h << endl; }
template<typename T, typename...U> void _dbg(const char *sdbg, T h, U... a) {
    while (*sdbg != ',') cerr << *sdbg++; cerr << " = " << h << ", "; _dbg(sdbg + 1, a...);
}
template<typename T> ostream& operator<<(ostream &os, vector<T> v) {
    os << "["; for (int i = 0; i < sz(v) - 1; i++) os << v[i] << ", "; os << v[sz(v) - 1]; os << "]";
    return os;
}
template<typename T, typename U> ostream& operator<<(ostream &os, pair<T, U> p) {
    os << "(" << p.first << ", " << p.second << ")"; 
    return os;
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int NMAX = 100005;

vector< vector<int> > g(NMAX, vector<int>());
bool visited[NMAX];
int ans;

void dfs(int u) {
    visited[u] = true;
    for (int v : g[u]) {
        if (!visited[v]) dfs(v);
    }
}

int main() {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    cin.sync_with_stdio(false); cin.tie(0); cin.exceptions(cin.failbit);
    memset(visited, NMAX, false);
    int N, M;
    cin >> N >> M;
    rep(ii, 0, M) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            dfs(i);
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}