【小码匠自习室】一道题3种解法：广搜+深搜+并查集，本宝宝困了，明天继续研究

小码匠

发布于 2022-12-06 10:55:02

5480

发布于 2022-12-06 10:55:02

文章被收录于专栏：小码匠和老码农

让悲伤不再重来

我的代码还在调试中，我🥱了，明天继续。。。

题目

C - Connect Cities

https://atcoder.jp/contests/abl/tasks/abl_c

問題描述

有N个城市（编号1到N）和M条双向道路（编号1到M）。道路 i 连接城市 A_i 和城市 B_i 。

Snuke 可以执行以下操作 0 次或更多次。

选择两个没有直接连接道路的不同城市，并在它们之间建造一条道路。

完成后，您应该能够通过沿着道路（可能多次）从任何城市到达任何城市。

要达到目标，最少要修建多少条道路？

制約

2 \leq N \leq 100,000
1 \leq M \leq 100,000
1 \leq A_i < B_i \leq N
没有两条道路连接同一城市。
所有输入都是整数。

入力

输入从标准输入以下列格式给出。

N M
A_1 B_1
:
A_M B_M

出力

打印出你的答案。

入力例 1

3 1
1 2

出力例 1

首先，有3个城市，城市 1 和城市 2 之间有一条道路。

例如，Snuke 可以通过在城市 1 和城市 3 之间修建一条道路来实现他的目标。修好路后

您可以直接在城市 1 和 2 之间旅行。
您可以直接在城市 1 和 3 之间旅行。
您可以通过两条路在城市 2 和 3 之间旅行。(2-1-3)

题解

小码匠

思路

代码：并查集

参考

题解1

思路

如果所有道路都是连通的，它将是0，不需要修路。

如果有2个连通分量，整体可以通过1条边连接
如果有3个连通分量，则整体可以通过 2 条边连接

一般来说，如果有 K 个连通分量，则可以通过 K-1 条边连接整体。

相反，添加一条边不能将连接组件的数量减少两个以上。因此，如果有 K 个连通分量，则至少需要 K-1 条边。

综上所述，

找到连接组件的数量
减去 1

我发现它是通过以下方式需要的。

Union-Find

说到组，Union-Find。Union-Find 允许对连接的组件进行有效分组。

具体来说，对于每条边 (u,v)，

代码

uf.merge(u, v);

最后，在计算组数时，请执行以下操作：

Union-Find 中的每个组都是一棵有根树
因此，在Union-Find的元素中找到“根”的数量就足够了
Union-Find中的元素v是否为根可以通过uf.root(v) == v是否为真来判断

基于以上，可以如下实现。复杂度为 O((N+M)α(N))) 。

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

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        uf.merge(a, b);
    }
    int res = 0;
    for (int i = 0; i < N; ++i) if (uf.root(i) == i) ++res;
     cout << res - 1 << endl;
}

参考代码

struct UnionFind {
    int num;
    vector<int> rs, ps;
    UnionFind() {}
    UnionFind(int n) : num(n), rs(n, 1), ps(n, 0) { iota(ps.begin(), ps.end(), 0); }
    int find(int x) {
        return (x == ps[x] ? x : ps[x] = find(ps[x]));
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rs[x] < rs[y]) swap(x, y);
        rs[x] += rs[y];
        ps[y] = x;
        num--;
    }
    int size(int x) {
        return rs[find(x)];
    }
    int count() const {
        return num;
    }
};

//INSERT ABOVE HERE
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);


    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        uf.unite(a, b);
    }
    cout << uf.count() - 1 << newl;
    return 0;
}

题解2

思路：DFS

还有基于图搜索解决方案的解决方案。所说的DFS

从图上的点 v 开始
递归调用与之相连的点

因此，对于每个连通分量，在其中的一点 v 上调用递归函数 dfs(v) 将访问连通分量中包含 v 的所有顶点。

基于以上考虑，可以通过下面的实现来统计连接组件的数量。

代码

int counter = 0;
vector<bool> seen(N, false);
for (int v = 0; v < N; ++v) {
    if (seen[v]) continue;
    dfs(v);
    ++counter;
}

换句话说，重复搜索，直到搜索完所有顶点。

每次调用 dfs(v) 时，都会调用“新连通分量中的顶点 v”。

因此，如果您在调用 dfs(v) 时增加 counter，则 counter 的值将是您想要的连接组件的数量。

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

void dfs(const Graph &G, vector<bool> &seen, int v) {
    seen[v] = true;
    for (auto nv : G[v]) if (!seen[nv]) dfs(G, seen, nv);
}

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b), G[b].push_back(a);
    }
    int res = 0;
    vector<bool> seen(N, false);
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue;
        dfs(G, seen, v);
        ++res;
    }
    cout << res - 1 << endl;
}

题解3

思路：BFS

BFS也可以解决，思路和DFS完全一样。

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

void bfs(const Graph &G, vector<int> &dist, int s) {
    dist[s] = 0;
    queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (auto nv : G[v]) {
            if (dist[nv] == -1) {
                dist[nv] = dist[v] + 1;
                que.push(nv);
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b), G[b].push_back(a);
    }
    int res = 0;
    vector<int> dist(N, -1);
    for (int v = 0; v < N; ++v) {
        if (dist[v] != -1) continue;
        bfs(G, dist, v);
        ++res;
    }
    cout << res - 1 << endl;
}

题解4

思路

问题可以重述如下。

有一个有 N 个顶点和 M 个边的无向图 G，其中第 i 条边连接第 A_i 顶点和第 B_i 顶点。连接 G 必须添加的最小边数是多少？

为了解决这个问题，我们关注连接组件的数量。例如，如果有 1 个连通分量，则答案为 0，因为条件已经满足。此外，如果有 2 个连通分量，则答案为 1，因为通过在从两个连通分量中选择一个的顶点之间添加一条边来满足条件。

这样思考，我们可以看到，通过从两个不同的连通分量中逐一选择顶点并添加连接两个顶点的边，可以将连通分量的数量减少一个。所以答案是（G 的连通分量数）-1。

有几种技术可以在图中找到连通分量的数量。

并查集（Union-Find）

Union-Find是将每一组视为一棵树的数据结构，通过两个顶点所属的树的根是否相同来判断两个顶点是否在同一个组中。在 C++ 的情况下，可以使用 ACL dsu 轻松实现，可以通过包含 atcoder/all 或 atcoder/dsu 来使用。

使用DFS或BFS

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
    int n,m;
    cin>>n>>m;
  
    //n頂点のグラフgを用意する
    dsu g(n);
  
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
    
        //入力の1がgでの0に対応
        a--;b--;
    
        //辺を追加する
        g.merge(a,b);
    }
 
    //連結成分の数-1が答え
    int ans=g.groups().size()-1;
  
    cout<<ans<<endl;
}

END

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-10-12，如有侵权请联系 cloudcommunity@tencent.com 删除

c++