题解 CF1198C 【Matching vs Independent Set】
ljc20020730
2019-08-16 21:09:26
这是一个非常**无脑**的随机化算法。
首先你需要知道一个东西叫做$random\_shuffle()$这个函数可以帮助你随机地打乱一个数组。
判断独立集，如果数据存在一个合法的独立集的话，那么显然随机选择一个点，它有$\frac{1}{3}$的概率在独立集中，一旦确定了一个点在独立集中，我们显然可以构造出一个合法的独立集了。
如何保证正确性？我只需要多做几次就行了。
判断匹配也是相同的道理。
所以，这个题目可以在$O(n)$的复杂度内随机化出解。
```cpp
# include <bits/stdc++.h>
using namespace std;
const int N=3e5+10,M=5e5+10;
vector<int>E[N];
struct node{
int u,v;
}Edge[M];
bool vis[N];
int n,m,p[N],e[M],t[N];
bool work1()
{
memset(vis,false,sizeof(vis));
int cnt = 0; random_shuffle(p+1,p+1+3*n);
for (int i=1;i<=3*n;i++) if (!vis[p[i]]) {
t[++cnt]=p[i];
if (cnt == n) {
puts("IndSet");
for (int j=1;j<=cnt;j++) printf("%d ",t[j]);
puts(""); return true;
}
for (int j=0;j<(int)E[p[i]].size();j++) vis[E[p[i]][j]]=true;
}
return false;
}
bool work2()
{
memset(vis,false,sizeof(vis));
int cnt = 0; random_shuffle(e+1,e+1+m);
for (int i=1;i<=m;i++) {
int u=Edge[e[i]].u,v=Edge[e[i]].v;
if (vis[u] || vis[v]) continue;
vis[u] = vis[v] = 1;
t[++cnt] = e[i];
if (cnt == n) {
puts("Matching");
for (int j=1;j<=cnt;j++) printf("%d ",t[j]);
puts(""); return true;
}
}
return false;
}
int main()
{
srand(time(NULL)*100007);
int T; scanf("%d",&T);
while (T--) {
scanf("%d%d",&n,&m);
for (int i=1;i<=3*n;i++) p[i]=i,E[i].clear();
for (int i=1;i<=m;i++) e[i]=i;
for (int i=1;i<=m;i++) {
int u,v; scanf("%d%d",&u,&v);
Edge[i]=(node){u,v};
E[u].push_back(v);
E[v].push_back(u);
}
int flag = 0;
for (int i=1;i<=10;i++)
if (work1()) { flag = 1; break;}
if (flag) continue;
flag = 0;
for (int i=1;i<=10;i++)
if (work2()) { flag = 1; break;}
if (flag) continue;
puts("Impossible");
}
return 0;
}
```