Bigraph Extension HDU - 7135
有一个2*n（n为偶数，n < 1e3)个点的二分图，已经连好了m条边，这m条边保证任意两条边不含公共点。
求最少添加多少条边，使得这个图任意两点连通，且最长简单路径所含边数 > n。输出最小字典序的方案。
``
`
`
``
``
``
思路，不难想到是要建一个2*n的环。那么此题关键点是要构造字典序最小的方案，那么我们每次找字典序最小的点来建边即可。用并查集维护，保证连的点不成环。
那么对于最后一条边，也就是两个度数为1的点连边使图成环即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=2e3+11;
vector<P> ans;
ll fa[maxn],d[maxn];
ll n,m;
ll found(ll x){return fa[x]==x?x:fa[x]=found(fa[x]);}
void solve1(){
ll e=0;
for(ll i=1;i<=n;i++){
while(d[i]<2){
for(ll j=n+1;j<=2*n;j++){
if(d[j]<2){
ll fi=found(i),fj=found(j);
if(fi==fj) continue;
d[i]++,d[j]++;
ans.push_back({i,j});
fa[fi]=fj;
e++;
if(e>=2*n-m-1) return ;
break;
}
}
}
}
}
void solve2(){
ll u,v;
for(ll i=1;i<=2*n;i++){
if(d[i]==1){u=i;break;}
}
for(ll i=1;i<=2*n;i++){
if(d[i]==1 && i!=u){v=i;break;}
}
ans.push_back({u,v});
cout<<ans.size()<<endl;
for(auto i=ans.begin();i!=ans.end();i++){
cout<<(*i).first<<" "<<(*i).second-n<<endl;
}
return ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll ca;cin>>ca;
while(ca--){
cin>>n>>m;
for(ll i=1;i<=2*n;i++) fa[i]=i;
ans.clear();memset(d,0,sizeof(d));
for(ll i=1;i<=m;i++){
ll u,v;cin>>u>>v;
v=v+n;
d[u]++,d[v]++;
fa[u]=v;
}
solve1();
solve2();
}
return 0;
}
|