Count Connected Components（判断连通块数量）

题目描述：

You are given a simple undirected graph with \(N\) vertices numbered \(1\) to \(N\) and \(M\) edges numbered \(1\) to \(M\). Edge \(i\) connects vertex \(u_i\) and vertex \(v_i\).Find the number of connected components in this graph.

输入描述：

\(NM\)

\(u_1 v_1\)

\(u_2 v_2\)

\(...\)

\(u_m v_m\)

输出描述：

Print the answer.

样例1：

input:

5 3
1 2
1 3
4 5

ouput:

2

样例2：

input:

5 0

output:

5

样例3：

input:

4 6
1 2
1 3
1 4
2 3
2 4
3 4

ouput:

1

AC代码：

// 方法一：并查集
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m;
int f[N];
int d[N];

int find(int x)
{
    if(x != f[x])
        f[x] = find(f[x]);

    return f[x];
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> m;

    for(int i = 1; i <= n; i ++)
        f[i] = i;

    int ans = 0;

    for(int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;

        int fa = find(a), fb = find(b);

        if(fa != fb)
        {
            f[fa] = fb;
        }
    }

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

        if(fi == i)
            ans ++;
    }

    cout << ans << '\n';

    return 0;
}

// 方法二：邻接表+DFS
#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 1e5 + 10;

int T = 1;
int n, m;
bool st[N];
int h[N], e[M], ne[M], idx;

void dfs(int u)
{
    st[u] = 1;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];

        if(!st[j])
        {
            dfs(j);
        }
    }
}

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

void solve()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    for(int i = 1; i <= m; i ++)
    {
        int a, b;
        cin >> a >> b;

        add(a, b);
        add(b, a);
    }

    int ans = 0;

    for(int i = 1; i <= n; i ++)
        if(!st[i])
        {
            ans ++;
            dfs(i);
        }

    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    // cin >> T;
    // scanf("%d", &T);

    while (T--)
        solve();

    return 0;
}

// 方法三：vector+DFS
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m;
// 也可以用vector<int> g[N];
vector<vector<int>> g(N);
// bool st[N];
vector<int> vis(N);

void dfs(int u)
{
    vis[u] = 1;

    for (auto j : g[u])
    {
        if (vis[j])
            continue;

        dfs(j);
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;

        -- u, -- v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    int ans = 0;

    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            ans++;
            dfs(i);
        }
    }

    cout << ans << "\n";

    return 0;
}