題意 ：

• 給兩片n個節點的森林，每次分別在兩片森林的u和v節點之間加一條邊，要求仍然是兩片森林，求最多能加多少條邊。
• $1\le n\le 1000,0\le m1,m2<n$

思路 ：

• 并查集 + 暴力枚舉，直接枚舉所有邊。$p.s.$并查集查詢時間復雜度為比較小的常數。

#include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <vector> #include <unordered_map> #include <unordered_set> #include <set> #include <map> #define endl '\n' #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; const double pi = acos(-1); typedef long long ll;//8.18const int N = 1e3 + 10;int p1[N], p2[N];int find1(int x) {if (p1[x] != x) p1[x] = find1(p1[x]);return p1[x]; }int find2(int x) {if (p2[x] != x) p2[x] = find2(p2[x]);return p2[x]; }void solve() {int n, m1, m2;cin >> n >> m1 >> m2;for (int i = 1; i <= n; i ++ ) p1[i] = i, p2[i] = i;for (int i = 1; i <= m1; i ++ ){int u, v;cin >> u >> v;u = find1(u), v = find2(v);if (u != v) p1[u] = v;}for (int i = 1; i <= m2; i ++ ){int u, v;cin >> u >> v;u = find2(u), v = find2(v);if (u != v) p2[u] = v;}vector<pair<int, int>> ve;for (int i = 1; i <= n; i ++ )for (int j = i + 1; j <= n; j ++ )if (find1(i) != find1(j) && find2(i) != find2(j)){p1[find1(i)] = find1(j);p2[find2(i)] = find2(j);ve.push_back({i, j});}cout << ve.size() << endl;for (int i = 0; i < ve.size(); i ++ ) cout << ve[i].first << " " << ve[i].second << endl; }int main() {IOS;// int T; // cin >> T; // // while (T -- ) // { // solve(); // }solve();return 0; }

總結

以上是生活随笔為你收集整理的Mocha and Diana (Easy Version) 并查集维护两片森林的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。