Theme:[ABC284C] Count Connected Components

#include <bits/stdc++.h>
using namespace std;
vector<int>G[110]; //使用 邻接表 存图
bool vis[110]; //标记节点是否被访问
void dfs(int u){
    vis[u]=true;
    for (auto &v : G[u]) if(!vis [v]) dfs (v); //遍历所有可以访问且未被访问的节点
    return ;
}
int main () {
    int n, m, ans=0;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v); //邻接表建图
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis [i]){
            dfs (i);
            ans++;
        }
    }
    cout << ans;
    return 0;
}

上述代码来源：Lyu_echo

下述代码来源:me

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<cstring>
typedef long long ll;
using namespace std;
const int N = 5e4 + 10;
vector<int> a;
vector<int> b;
int h[N], e[N], ne[N], idx;
bool st[N];
int cnt;

void add(int a, int b) {

    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int deep) {

    st[deep] = true;
    for (int i = h[deep]; i != -1; i = ne[i]) {

        int j = e[i];

        if (!st[j]) {

            dfs(j);

        }
    }

}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {

        int a1, b1;
        cin >> a1 >> b1;

        add(a1, b1), add(b1, a1);
    }

    for (int i = 1; i <= n; i++) {


        if (!st[i]) {

            cnt++;

        }
        dfs(i);
    }
    if (m)cout << cnt << '\n';
    else cout << n << '\n';
    return 0;
}

大幅度减少了思维的深度