CF1239D Catowice City 题解

题意：

下周末将在卡托维兹市举行猫比赛。然而，评委成员和参赛者尚未确定。卡托维兹市有 \(n\) 名居民和 \(n\) 只猫，每个居民的家中都有一只猫。居民和猫的编号分别为 1 到 \(n\)，第 \(i\) 只猫住在第 \(i\) 名居民的家中。

每个卡托维兹市的居民与几只猫交朋友，其中包括他家中的那只猫。为了举办比赛，至少需要一名评委和一名猫参赛者。当然，每个评委都不应认识任何参赛者。为了比赛的成功举办，评委人数加上参赛者人数应该等于 \(n\)。

请帮助卡托维兹市的居民为即将举行的比赛选择评委和参赛者，或确定无法实现。

输入格式：

第一行包含一个整数 \(t\)（\(1 \leq t \leq 100000\)），表示测试用例的数量。接下来是 \(t\) 个测试用例的描述，每个描述如下：

第一行包含整数 \(n\) 和 \(m\)（\(1 \leq n \leq m \leq 10^6\)），表示卡托维兹市居民的数量和居民与猫之间的友谊对数。

接下来的 \(m\) 行中，每行包含整数 \(a_i\) 和 \(b_i\)（\(1 \leq a_i, b_i \leq n\)），表示第 \(a_i\) 名居民与第 \(b_i\) 只猫相识。保证每对居民和猫的组合最多只列出一次。

不同的测试用例之间用空行分隔。

保证所有测试用例中 \(n\) 的总和最多为 \(10^6\)，\(m\) 的总和最多为 \(10^6\)。

输出格式：

对于每个测试用例，打印：

如果无法选择评委和参赛者，则打印 "No"。否则打印 "Yes"。

在第二行打印两个整数 \(j\) 和 \(p\)（\(1 \leq j, 1 \leq p, j+p=n\)），表示评委成员和比赛参与者的数量。

在第三行打印 \(j\) 个从 1 到 \(n\) 的不同整数，表示组成评委团的居民的索引。

在第四行打印 \(p\) 个从 1 到 \(n\) 的不同整数，表示将参加比赛的猫的索引。如果存在多个正确答案，则可以任意打印其中一个。

注意到每只猫都和自己的主人认识，所以我们可以把猫和自己的主人看作一个节点

则此时任意的一个强连通分量，要么全部选猫，要么全部选人。

于是我们钦定出度为 \(0\) 的那个强连通分量全部选人，然后其他点全部选猫。如果只有一个强连通分量则无解。

时间复杂度 \(\mathcal{O}(n+m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))

int n,m,pos=1,top,scnt,head[N],dfn[N],low[N],stk[N],sz[N],scc[N]; bitset<N> ins;
struct Edge { int u,v,next; } e[N];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void Tarjan(int u)
{
    static int tim = 0;
    dfn[u] = low[u] = ++tim; ins[stk[++top] = u] = 1;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        if(!dfn[v]) {
            Tarjan(v); down(low[u], low[v]);
        }else if(ins[v]) { down(low[u], dfn[v]); }
    }
    if(low[u] == dfn[u]) {
        ++scnt;
        for(int p = 0; p != u; ) {
            p = stk[top--]; scc[p] = scnt; ins[p] = 0; ++sz[scnt];
        }
    }
}
void solve()
{
    cin >> n >> m; scnt = top = 0; pos = 1;
    for(int i = 1; i <= n; i++) head[i] = sz[i] = dfn[i] = ins[i] = 0;
    for(int i = 1,u,v; i <= m; i++) { cin >> u >> v; if(u != v) addEdge(u,v); }
    for(int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i);
    // cout << "scnt = " << scnt << '\n';
    if(scnt == 1) return cout << "No" << '\n', void(0);
    cout << "Yes\n" << sz[1] << ' ' << n - sz[1] << '\n';
    for(int i = 1; i <= n; i++) if(scc[i] == 1) { cout << i << ' '; } cout << '\n';
    for(int i = 1; i <= n; i++) if(scc[i] != 1) { cout << i << ' '; } cout << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}