D2. Mocha and Diana (Hard Version)
https://codeforces.com/contest/1559/problem/D2
题目大意
给出两个图,现在可以进行一个操作,就是选出两个点 \(x,y\),并且在两个图中给 \(x,y\)之间连一条边,这两个点必须满足连边之前不在同一个联通块内。询问你最多可以连多少条边?
解题思路
\(D1\)的解法是\(n^2\) 的并查集,但是此题\(n^2\)显然过不了。
因此就是需要优化一下 \(n^2\)的枚举过程,首先我们可以固定一个点,比如说点 \(1\)(因为\(1\)点最小,好维护),那么我们只需要将其他点和 \(1\)进行连边即可。
这里并差集合并时需要按秩合并,即节点编号大的点指向节点编号小的点,因为我们保证\(1\)号点为根结点。
同时维护两个数据结构(这里用栈)存储。
即枚举\(n\)个点并判断(假如当前枚举点为\(i\)):
\(i\)点在两个图中都和 \(1\)处于同一个并查集中,则 \(i\)点不会对答案造成贡献
\(i\)点在两个图中都不与 \(1\)处于同一个并查集中,则此时 \(i\)可以直接与 \(1\)连边,直接存储答案即可
当\(i\)点在第一个图中与\(1\)处于同一个并查集,但在第二个图中没有,则将 \(i\)点存到第二个栈中
当\(i\)点在第一个图中不与\(1\)处于同一个并查集中但在第二个图中与\(1\)处于同一个并差集中,则将\(i\)点存储到第一个栈中
我们可以发现直接将两个栈的元素取出连边是满足题意的,取出之前需要判断这个点是否在两个图中都与 \(1\)处于同一个并差集中,如果是则需要直接将其出栈,因为这个点对答案没有用,而且每次取出之前都需要判断,因为这个点可能受前面连过的点的影响。
假如第一个栈顶元素为\(i\),第二个栈顶元素为\(j\),那么\(i\)点在第一个图中不与\(1\)处于同一个并差集中,而\(j\)点在第一个图中所处并差集的根结点就是\(1\),在第二个图中刚好相反,所以可以直接将\(i,j\)之间连边即可,这样相当于在两个图中都是\(1\)和对应点相合并。
Code
#include <bits/stdc++.h>
#define ll long long
#define qc ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define pb push_back
#define V vector
using namespace std;
const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int f[N][3];
V<int>v1,v2;
int find(int x,int ff){
if(x == f[x][ff])
return x;
else {
return f[x][ff] = find(f[x][ff],ff);
}
}
void solve(){
int n,m1,m2;
cin >> n >> m1 >> m2;
for(int i = 1; i <= n;i++)
f[i][1] = f[i][2] = i;
V<PII>ans;
for(int i = 1; i <= m1;i ++){
int x,y;
cin >> x >> y;
x = find(x,1);
y = find(y,1);
f[max(x,y)][1] = min(x,y);
}
for(int i = 1; i <= m2; i++){
int x,y;
cin >> x >> y;
x = find(x,2);
y = find(y,2);
f[max(x,y)][2] = min(x,y);
}
for(int i = 2; i <= n; i++){
int x1 = find(i,1);
int x2 = find(i,2);
if(x1 == 1 && x2 == 1)
continue;
if(x1 != 1 && x2 != 1){
ans.pb({i,1});
f[x1][1] = 1;
f[x2][2] = 1;
continue;
}
if(x1 != 1)
v1.pb(i);
if(x2 != 1)
v2.pb(i);
}
while(!v1.empty() && !v2.empty()){
if(find(v1.back(),1) == 1 && find(v1.back(),2) == 1){
v1.pop_back();
continue;
}
if(find(v2.back(),1) == 1 && find(v2.back(),2) == 1){
v2.pop_back();
continue;
}
ans.pb({v1.back(),v2.back()});
int x = find(v1.back(),1),y = find(v2.back(),1);
f[x][1] = y;
x = find(v1.back(),2), y = find(v2.back(),2);
f[x][2] = y;
v1.pop_back();
v2.pop_back();
}
cout << ans.size() << "\n";
for(auto p : ans){
cout << p.fi << " " << p.se <<"\n";
}
}
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
qc;
int T = 1;
//cin >> T;
while(T--){
solve();
}
return 0;
}