题解 CF1239D 【Catowice City】

2019-10-21 07:56:58


大致题意:有 $n$ 个人和 $n$ 只猫,每个人都认识编号与他相同的猫和另外一些猫,现在需要从人和猫中选出共 $n$ 个,使得其中既有人,也有猫,并且所有选出的人都不认识任何选出的猫。

思路:

首先,同一个编号的人和猫,必须选且仅选一个。为什么?感性证明一下(可能有误):假设选了 $r$ 个人, $n-r$ 个猫,如果选中的人和猫的编号的集合有交集,那么这种方案肯定不合法。而所有人和所有猫的集合大小都是 $n$ 且人和猫的编号一一对应,所以没有被选中的人,他对应的猫一定会被选中。

简而言之,选出的人的集合与选出的猫的集合互为补集。

那么考虑人认识猫的情况。假设人 $R$ 认识猫 $C$ ,套用2-SAT的思想,那么选了人 $R$ 就不能选猫 $C$ ,则根据上面的结论,一旦选了 $R$ 就必须选编号为 $C$ 的人。

因此,对于所有的关系,从 $R$ 向编号为 $C$ 的人连一条有向边,缩点后如果所有点在一个强连通分量里则无解,否则选择一个出度为0的强连通分量即可。

代码是考场上写的,稍微有点丑:

#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;
}