题解 CF1239D 【Catowice City】
SIGSEGV
2019-10-21 07:56:58
大致题意：有$n$个人和$n$只猫，每个人都认识编号与他相同的猫和另外一些猫，现在需要从人和猫中选出共$n$个，使得其中既有人，也有猫，并且所有选出的人都不认识任何选出的猫。
思路：
首先，同一个编号的人和猫，必须选且仅选一个。为什么？感性证明一下（可能有误）：假设选了$r$个人，$n-r$个猫，如果选中的人和猫的编号的集合有交集，那么这种方案肯定不合法。而所有人和所有猫的集合大小都是$n$且人和猫的编号一一对应，所以没有被选中的人，他对应的猫一定会被选中。
简而言之，选出的人的集合与选出的猫的集合互为补集。
那么考虑人认识猫的情况。假设人$R$认识猫$C$,套用2-SAT的思想，那么选了人$R$就不能选猫$C$，则根据上面的结论，一旦选了$R$就必须选编号为$C$的人。
因此，对于所有的关系，从$R$向编号为$C$的人连一条有向边，缩点后如果所有点在一个强连通分量里则无解，否则选择一个**出度为0**的强连通分量即可。
代码是考场上写的，稍微有点丑:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
int n,m;
vector<int> e[N];
int dfn[N],scc_idx[N],low[N],tim,idx,sz[N],deg[N];
bool vis[N];stack<int> stk;
void tarjan(int pos) //Tarjan
{
dfn[pos] = low[pos] = ++tim;vis[pos] = 1;stk.push(pos);
for (auto &i : e[pos])
if (!dfn[i]) tarjan(i),low[pos] = min(low[pos],low[i]);
else if (vis[i]) low[pos] = min(low[pos],dfn[i]);
if (dfn[pos] == low[pos])
{
++idx;
while (!stk.empty())
{
int nd = stk.top();stk.pop();
vis[nd] = 0;scc_idx[nd] = idx;++sz[idx];
if (nd == pos) break;
}
}
}
int main ()
{
ios::sync_with_stdio(false);
int T;cin >> T;
while (T--)
{
cin >> n >> m;
tim = idx = 0;
int t1,t2;
for (int i = 1;i <= n;i++) e[i].clear();
for (int i = 1;i <= m;i++)
{
cin >> t1 >> t2;
if (t1 != t2) e[t1].push_back(t2);//连边
}
for (int i = 1;i <= n;i++)
scc_idx[i] = sz[i] = dfn[i] = low[i] = deg[i] = vis[i] = 0;//记得多组数据的题的初始化
for (int i = 1;i <= n;i++)
if (!dfn[i]) tarjan(i);
for (int i = 1;i <= n;i++)
for (auto &j : e[i])
if (scc_idx[i] != scc_idx[j]) ++deg[scc_idx[i]]; //计算出度
if (sz[scc_idx[1]] == n) { puts("NO");continue; }//无解情况
bool fl = 0;
for (int i = 1;i <= idx;i++)
if (!deg[i] && sz[i]) //有解
{
puts("YES");fl = 1;
vector<int> ans[2];
for (int j = 1;j <= n;j++)
ans[scc_idx[j] == i].push_back(j);
printf("%d %d\n",ans[1].size(),ans[0].size());
for (auto &i : ans[1]) printf("%d ",i);
puts("");
for (auto &i : ans[0]) printf("%d ",i);
puts("");
break;
}
if (!fl) puts("NO");
}
return 0;
}
```