In the Catowice city next weekend the cat contest will be held. However, the jury members and the contestants haven't been selected yet. There are 𝑛 residents and 𝑛 cats in the Catowice, and each resident has exactly one cat living in his house. The residents and cats are numbered with integers from 1 to 𝑛, where the 𝑖-th cat is living in the house of 𝑖-th resident.

Each Catowice resident is in friendship with several cats, including the one living in his house. In order to conduct a contest, at least one jury member is needed and at least one cat contestant is needed. Of course, every jury member should know none of the contestants. For the contest to be successful, it's also needed that the number of jury members plus the number of contestants is equal to 𝑛.

Please help Catowice residents to select the jury and the contestants for the upcoming competition, or determine that it's impossible to do.

链接🔗

「CodeForces 1239D」Catowice City

题解

第i个人，肯定认识第i只猫，又因为必须选的人和猫总数为n，所以该问题可以抽象成2-sat问题
考虑建边，如果i认识第j只猫，那么选了i人必须选j人，因为无法选j猫，同理连上 j猫和i猫的边
(i -> j) 与 ( j' -> i')
我们发现，人不会有到猫的边，并且猫的边与人的边是相反的，所以强联通缩点后构成的DAG一定也是相反的，我们考虑构造出一个选法，使得至少一个人，一个猫
我们考虑从人的图中选出无入边的一个连通块，那么该连通块在猫图中，一定无出边，所以不会产生互斥反应
接着考虑无解情况，很显然当且近当存在两个连通块时，无解

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxd = 2e6+10;
struct edge 
{
    int v, net;
} e[maxd<<1];
int f[maxd], eid;

void insert(int a,int b)
{
    e[eid].v = b;
    e[eid].net = f[a];
    f[a] = eid++;
}
int dfn[maxd], low[maxd],idx = 0;
int belong[maxd], scc = 0; 
int s[maxd], top = 0,n,m,sz[2],ans[maxd]; 
bool in_stack[maxd];
void init(int n)
{
    fill(f,f+1+n,-1);
    fill(dfn,dfn+1+n,0);
    sz[1] =sz[0] = scc = idx = eid = 0;
}
void tarjan(int u) 
{
    dfn[u] = low[u] = ++idx;
    s[top++] = u;
    in_stack[u] = true;
    for (int i = f[u]; i != -1; i = e[i].net) 
    {
        int v = e[i].v;
        if (!dfn[v]) 
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } 
        else if (in_stack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]) 
    {
        ++scc;
        do 
        {
            belong[s[--top]] = scc;
            in_stack[s[top]] = false;
        } while (s[top] != u);
    }
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    int t; scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        init(n*2);
        for(int i=1;i<=m;i++)
        {
            int x,y; scanf("%d %d",&x,&y);
            if(x == y) continue;
            insert(x,y),insert(y+n,x+n);
        }
        for(int i=1;i<=2*n;i++)
            if(!dfn[i]) tarjan(i);
        // for(int i=1;i<=2*n;i++)
        // {
        //     printf("%d %d\n",i,belong[i]);
        // }
        if(scc == 2)
        {
            printf("No\n");
            continue;
        }
        int now = 1;
        for(int i=1;i<=n;i++)
            if(belong[i] == 1) now=0;
        for(int i=1;i<=n;i++)
        {
            if(belong[i+now*n] == 1) ans[i] = now,sz[now]++;
            else sz[now^1]++, ans[i]=now^1;
        }
        printf("Yes\n%d %d\n",sz[0],sz[1]);
        for(int i=1;i<=n;i++) if(!ans[i]) printf("%d ",i);
        putchar(10);
        for(int i=1;i<=n;i++) if(ans[i]) printf("%d ",i);
        putchar(10);
    }
    return 0;
}