题解 CF1239D 【Catowice City】

81179332_ · 2020-06-27 16:09:10 · 题解

这是一个二分图，由于第 i 只猫和第 i 个人不能都选，所以我们可以将第 i 个人和第 i 只猫缩成一个点

对于一条从 u 连向 v 的边，表示如果 u 选了人，则 v 不能选猫

容易发现，对于一个强连通分量中的点，要么全选人，要么全选猫

对于出度为 0 的强连通分量（即编号为 1），由于没有出边，它不可能影响任何点，所以我们不妨令其选人，其它所有点都选猫（选猫也不会影响其他点）

如果只有一个强连通分量，则无解

//timeuse:20min
const int N = 1000010,M = N;
int n,m;EE(1);
int dfn[N],low[N],idx;
int st[N],top,col[N],num,siz[N];
bool vis[N];
void init()
{
    n = read(),m = read();
    for(int i = 1;i <= n;i++) head[i] = dfn[i] = low[i] = siz[i] = 0;
    ecnt = 1,num = idx = 0;
}
void Tarjan(int u)
{
    dfn[u] = low[u] = ++idx,vis[u] = 1,st[++top] = u;
    for(int i = head[u];i;i = e[i].nxt)
    {
        int v = e[i].to;
        if(!dfn[v]) Tarjan(v),low[u] = min(low[u],low[v]);
        else if(vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        num++;
        int v = st[top--];
        col[v] = num,vis[v] = 0,siz[num]++;
        while(st[top + 1] != u)
        {
            int v = st[top--];
            col[v] = num,vis[v] = 0,siz[num]++;
        }
    }
}
void solve()
{
    for(int i = 1;i <= m;i++)
    {
        int x = read(),y = read();
        if(x != y) add(x,y);
    }
    for(int i = 1;i <= n;i++) if(!dfn[i]) Tarjan(i);
    if(num == 1) { puts("No");return; }
    puts("Yes");pprint(siz[1]),fprint(n - siz[1]);
    for(int i = 1;i <= n;i++) if(col[i] == 1) pprint(i);putchar('\n');
    for(int i = 1;i <= n;i++) if(col[i] != 1) pprint(i);putchar('\n');
}
int main()
{
    int T = read();
    while(T--) init(),solve();
}