如果选择 $i$ 当陪审团成员，那么 $i$ 认识的猫一定不能参加
又因为总人数和猫数要为 $n$ ，那么 $i$ 认识的猫 的主人也一定要当陪审团成员（不然总数不够）
所以可以考虑这样构图，对每个人 $i$ 向认识的所有猫的主人 $j$ 连边，那么如果选择 $i$ ， $i$ 能到达的所有点都必须选择
所以对于一个点双，选其中任意一个就得选全部
如果这样构完图发现整个图只有一个点双，那么一定是 $ ext{No}$
否则考虑点双之间构成了一个 $DAG$ ，我们只要选择 $DAG$ 中任意一个没有出度的点双作为陪审团即可，剩下的点全选猫，用反证法容易证明一定合法
任意一个没有出度的点双其实考虑到 $Tarjan$ 的过程发现第一个缩起来的点双一定没有出度，证明同样可以反证法
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e6+7; int T,n,m; int fir[N],from[N<<1],to[N<<1],cntt; inline void add(int a,int b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; } int dfn[N],low[N],bel[N],dfs_clock,cnt; int st[N],Top; void Tarjan(int x) { st[++Top]=x; dfn[x]=low[x]=++dfs_clock; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(!dfn[v]) Tarjan(v),low[x]=min(low[x],low[v]); else if(!bel[v]) low[x]=min(low[x],dfn[v]); } if(low[x]!=dfn[x]) return; cnt++; while(st[Top]!=x) bel[st[Top--]]=cnt; bel[st[Top--]]=cnt; } int main() { T=read(); while(T--) { for(int i=1;i<=n;i++) fir[i]=dfn[i]=bel[i]=0; cntt=cnt=dfs_clock=0; n=read(),m=read(); int a,b; for(int i=1;i<=m;i++) { a=read(),b=read(); if(a==b) continue; add(a,b); } for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i); if(cnt==1) { printf("No "); continue; } int ans=0; for(int i=1;i<=n;i++) if(bel[i]==1) ans++; printf("Yes %d %d ",ans,n-ans); for(int i=1;i<=n;i++) if(bel[i]==1) printf("%d ",i); puts(""); for(int i=1;i<=n;i++) if(bel[i]!=1) printf("%d ",i); puts(""); } return 0; }