加强普法网站建设的通知,企业网站建设的一般要素包括,新做的网站怎样推广,专门做图的网站Bigraph Extension
题意#xff1a;
有2n个点#xff0c;n为偶数#xff0c;n个点属于集合A#xff0c;n个点属于集合B。起初在途中有m个无向边#xff0c;边的两侧端点分别在两个集合里#xff0c;任何两个边都没有公共交点。 现在你可以执行任意次操作#xff1a; 在…Bigraph Extension
题意
有2n个点n为偶数n个点属于集合An个点属于集合B。起初在途中有m个无向边边的两侧端点分别在两个集合里任何两个边都没有公共交点。 现在你可以执行任意次操作 在集合AB中分别选一个点这两个点没有直接的边相连现在给这两个点相连
在操作之后对于集合A中任意一个点集合B中任意一个点需要满足 这两个点是联通的 这两个点的最长简单路径是严格大于n的 问最少的加边数量并按照最小字典序输出连边方案
题解
构造题不过这个题的结论其实好猜具体证明就麻烦些 其实就是将2n个点构造成环现在已经有了m个点最小加边数就是2n-m 我们先不考虑环先考虑将所有点连通 然后就是考虑字典序的最小限制那我们就从小到达枚举集合A中的点再从小到大枚举B中的点通过维护并查集和度数数组来判断两个点是否连成链。这样就保证前2n-m-1条边的字典序最小。现在所有点已经联通了不过还缺一个边我们需要再加入一个边形成环我们遍历AB中度数为1的点连起来放在第2n-m条边的位置 官方题解的详细证明
代码
#pragma GCC diagnostic error -stdc11
#include algorithm
#include cmath
#include cstdio
#include cstring
#include ctime
#include iostream
#include map
#include queue
#include set
#include stack
#include unordered_map
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pairint, int pii;
const int mod 1e9 7;
const int MAXN 2e5 5;
const int inf 0x3f3f3f3f;
int fa[MAXN];
int in[MAXN];
vectorpii ans;
priority_queueint, vectorint, greaterint q;//最小堆
void init(int n)
{for (int i 1; i 2 * n; i) {fa[i] i;in[i] 0;}
}
int find(int x)
{if (fa[x] x)return x;elsereturn fa[x] find(fa[x]);
}
void combine(int u, int v)
{u find(u);v find(v);fa[u] v;
}
int main()
{int t;scanf(%d, t);while (t--) {ans.clear();int n, m;scanf(%d%d, n, m);init(n);for (int i 1; i m; i) {int u, v;scanf(%d%d, u, v);v n;combine(u, v);in[u];in[v];}for (int i n 1; i 2 * n; i)q.push(i);for (int i 1; i n; i) {queueint st;while (in[i] 2 !q.empty()) {int j q.top();q.pop();if (find(j) ! find(i)) {combine(i, j);in[i];in[j];ans.push_back({ i, j });}st.push(j);}while (!st.empty()) {int j st.front();st.pop();if (in[j] 2)q.push(j);}}int flag 0, p1 0, p2 0;for (int i 1; i n; i) {if (in[i] 1){p1 i;break;}}for (int i n 1; i 2 * n; i) {if (in[i] 1){p2 i;break;}}if(p1!0p2!0) {ans.push_back({ p1, p2 });
// printf(组成环p1%d,p2%d\n,p1,p2-n); }if (flag) {printf(-1\n);} else {printf(%d\n, ans.size());for (auto i : ans) {printf(%d %d\n, i.first, i.second - n);}}while (!q.empty())q.pop();}
}
