C++求联通块数量

本文使用了下面五种方法求联通块数量：

1. 并查集
2. 深度优先搜索DFS
3. 广度优先搜索BFS
4. Floyd
5. Kruskal

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
const int M = 10010;

int n, m;
vector<int> g[N];

int ans = 0;

// 1.并查集
int pre[N];
int find ( int x )
{
    return x == pre[x] ? pre[x] : pre[x] = find ( pre[x] );
}

void merge ( int x, int y )
{
    int rx = find ( x ), ry = find ( y );

    if ( rx != ry )
    {
        pre[rx] = ry;
    }
}

void solveA()
{

    for ( int i = 1; i <= n; i++ )
    {
        pre[i] = i;
    }

    for ( int i = 1; i <= m; i++ )
    {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back ( v );
        g[v].emplace_back ( u );
        merge ( u, v );
    }

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

    cout << ans;

}

// 2.深搜
int vis[N];

void dfs ( int x )
{
    for ( auto &u : g[x] )
    {
        if ( vis[u] )
        { continue; }

        vis[u] = true;
        dfs ( u );
    }
}

void solveB()
{
    for ( int i = 1; i <= m; i++ )
    {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back ( v );
        g[v].emplace_back ( u );
    }

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

    cout << ans;
}

// 3.广搜
void bfs ( int x )
{
    queue<int> q;
    q.emplace ( x );

    while ( !q.empty() )
    {
        int u = q.front();
        q.pop();

        for ( auto &v : g[u] )
        {
            if ( vis[v] )
            { continue; }

            vis[v] = true;
            q.emplace ( v );
        }
    }
}

void solveC()
{
    for ( int i = 1; i <= m; i++ )
    {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back ( v );
        g[v].emplace_back ( u );
    }

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

    cout << ans;
}

// 4.Floyd
int adj[N][N];
void solveD()
{
    for ( int i = 1; i <= n; i++ )
    {
        adj[i][i] = 1;
    }

    for ( int i = 1; i <= m; i++ )
    {
        int u, v;
        cin >> u >> v;
        adj[u][v] = adj[v][u] = 1;
    }

    ans = 0;

    for ( int k = 1; k <= n; k++ )
    {
        for ( int i = 1; i <= n; i++ )
        {
            for ( int j = 1; j <= n; j++ )
            {
                if ( adj[i][k] && adj[k][j] )
                {
                    adj[i][j] = 1;
                }
            }
        }
    }

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

            for ( int j = 1; j <= n; j++ )
            {
                if ( adj[i][j] )
                { vis[j] = true; }
            }
        }
    }

    cout << ans;
}

// 5.Kruskal 最小生成森林
struct Edge
{
    int u, v;
} e[M];

void solveE()
{
    for ( int i = 1; i <= n; i++ )
    {
        pre[i] = i;
    }

    for ( int i = 1; i <= m; i++ )
    {
        int u, v;
        cin >> u >> v;
        e[i] = {u, v};
    }

    ans = n;

    for ( int i = 1; i <= m; i++ )
    {
        int u = e[i].u, v = e[i].v;
        int ru = find ( u ), rv = find ( v );

        if ( ru != rv )
        {
            merge ( ru, rv );
            ans--;
        }
    }

    cout << ans;

}

// 

int main()
{
    cin >> n >> m;
//  solveA();
//  solveB();
//  solveC();
//  solveD();
    solveE();

    return 0;
}