CF1239D Catowice City

说在前面的：

其实本题在答案的统计上并没有另两篇题解讲的那么麻烦

如果你真正搞懂了tarjan，你会明白如果一个强连通分量有出边，由于它dfs的性质，一定会继续向下遍历，直到找到一个没有出度的强连通分量

因此，第一个被找到的强联通分量一定是没有出度的！

这样其余两篇题解的做法在过程上还可以被大幅简化

题解

首先，一个很简单的问题：为什么n个不可以都是猫呢？

因为必须至少有一个人

那么我们就必须把这个人放到无法产生任何影响的地方去

即一个人群（或仅一个人）

这个人群必须满足不会再对后续产生影响（因为连猫不合法，连人不如换个部分做人群）

即无出度

同时人群中也要保持强联通，因为如果有人不强联通，他就可以被分离出看成猫

因此问题转化为在一个有向图中找一个没有出度的强连通分量

在这个没有出度的强联通分量里的都是人，否则是猫

而我之前又说过第一个被找到的强联通分量一定是没有出度的，因此编号为1的强连通分量就是我们要找的

另外，显然的，如果只有一个强连通分量就是不合法的

代码

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}
const int N=1e6+5;
int h[N],st[N],lim,dfn[N],low[N],cnt,en,scc[N],sn,n,m,t,sz[N];
bool v[N];
struct edge{int n,v;}e[N];
inline void add(int x,int y){e[++en]=(edge){h[x],y};h[x]=en;}
void tarjan(int x){ //tarjan模板
    v[x]=1;
    st[++lim]=x;
    dfn[x]=low[x]=++cnt;
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else{
            if(v[y]) low[x]=min(low[x],dfn[y]);
        }
    }
    if(dfn[x]==low[x]){
        int top;
        sn++;
        for(;;){
            top=st[lim--];
            v[top]=0;
            scc[top]=sn;
            sz[sn]++; //sz[]是强连通分量的大小
            if(top==x) break;
        }
    }
}
void doit(){
    read(n);read(m);
    sn=cnt=en=lim=0;
    for(int i=1;i<=n;i++) h[i]=sz[i]=dfn[i]=0;
    for(int i=1,x,y;i<=m;i++){
        read(x);read(y);
        if(x==y) continue; //自己和自己的猫可忽略
        add(x,y);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    if(sn==1){ //只有一个强连通分量，不合法
        puts("No");
        return ;
    }
    printf("Yes\n%d %d\n",sz[1],n-sz[1]); //sz[1]是人的个数，减一减得到猫数
    for(int i=1;i<=n;i++) if(scc[i]==1) write(i),putchar(' ');puts(""); //第一个的都是人
    for(int i=1;i<=n;i++) if(scc[i]!=1) write(i),putchar(' ');puts(""); //否则是猫
}
signed main(){
    read(t);
    while(t--) doit();
}

(ps.本题清零初始化用memset会T在第三个点，要改用for)

赏

OIer