Problem Link

题目大意

给定 $n$ 个点 $m$ 条边的有向图。

• 一个点 $u$ 为一类点：当且仅当 $u$ 到其他的每个点的简单路径都唯一。
• 一个点 $u$ 为二类点：删去若干条边后，$u$ 是一类点，且原有的一类点依然是一类点。

否则一个点是三类点判定每个点是哪类点。

数据范围：$n\le 10^5,m\le 2\times 10^5$。

思路分析

首先进行缩点，一类点必须是没有入度的 SCC，如果这样的 SCC 不唯一，则所有点为三类点。

否则只需要考虑该 SCC，即考虑图强连通的情况，如果一类点不存在，那么所有点都是二类点。

然后考虑如何判定一个点是一类点：首先建立 dfs 树，如果有横叉边，则一定不为一类点。

否则 dfs 树上只有返祖边，可以归纳证明这样的点一定是一类点。

假设我们找到了一个一类点，考虑求出所有一类点：

考虑每个点被多少条返祖边覆盖，由于图强连通，那么覆盖次数 $\ge 1$。

如果一个点被 $>1$ 条返祖边覆盖，那么走到其父亲的路径不唯一。

否则设该返祖边为 $x\to y$，则 $u$ 为一类点当且仅当 $y$ 为一类点，从上到下递推即可。

然后尝试判断哪些点是二类点：

首先我们要知道哪些边可以删除：首先 dfs 树上的边删除后根的连通性改变，肯定不能删除。

其次一条返祖边 $x\to y$ 如果经过了一个一类点，那么删除后这个点不再是一类点，不能删除。

而其他边都能删除，我们的目标就是要删除若干条可以删除的返祖边，使得剩余的返祖边 $x\to y$ 唯一，且 $y$ 是二类点。

先判断经过每个点的不可删除的返祖边是否 $>1$ 条，然后在 dfs 过程中动态维护维护每个点子树中是否有这样的 $x$，用树状数组实现即可。

最后我们要找到一个合法的一类点作为根：

考虑其叶子，由于没有横叉边，因此每个叶子的入度为 $1$，那么对于每个叶子 $u$，把 $u$ 向其唯一入点合并（去处自环，不删除重边）。

实际上这就是在 dfs 树上不断缩叶子的过程中，最后停止的时候图上一定只剩唯一节点，这就是一个合法的根，否则说明不存在一类点。

用启发式合并维护该过程。

时间复杂度 $\mathcal O(m\log n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m;
vector <int> G[MAXN];
int dsu[MAXN];
int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }
struct FenwickTree {
	int tr[MAXN],s;
	void init() { memset(tr,0,sizeof(tr)); }
	void add(int x) { for(;x<=n;x+=x&-x) ++tr[x]; }
	int qry(int x) { for(s=0;x;x&=x-1) s+=tr[x]; return s; }
}	TR;
int dfn[MAXN],low[MAXN],dcnt,stk[MAXN],tp,col[MAXN],scnt;
bool ins[MAXN],ind[MAXN],inq[MAXN],vis[MAXN];
void tarjan(int u) {
	dfn[u]=low[u]=++dcnt,ins[stk[++tp]=u]=true;
	for(int v:G[u]) {
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(ins[v]) low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u]) {
		++scnt;
		while(ins[u]) col[stk[tp]]=scnt,ins[stk[tp--]]=false;
	}
}
int deg[MAXN];
vector <int> in[MAXN];
unordered_map <int,int> S[MAXN];
bool chk(int u) {
	memset(ins,0,sizeof(ins));
	memset(vis,0,sizeof(vis));
	bool ok=1;
	function<void(int)> dfs=[&](int x) {
		vis[x]=ins[x]=true;
		for(int y:G[x]) {
			if(!vis[y]) dfs(y);
			else ok&=ins[y];
		}
		ins[x]=false;
	};
	dfs(u);
	for(int i=1;i<=n;++i) ok&=vis[i];
	return ok;
}
int getrt() {
	for(int i=1;i<=n;++i) dsu[i]=i;
	for(int i=1;i<=n;++i) for(int j:G[i]) {
		++S[i][j],in[j].push_back(i),++deg[j];
	}
	for(int i=1;i<=n;++i) if(!deg[i]) return chk(i)?i:0;
	queue <int> Q;
	for(int i=1;i<=n;++i) if(deg[i]==1) Q.push(i);
	while(Q.size()) {
		int x=0,y=Q.front(); Q.pop();
		if(deg[y]!=1||dsu[y]!=y) continue;
		for(int k:in[y]) if(find(k)!=y) {
			x=find(k); break;
		}
		S[x].erase(y);
		auto it=S[y].find(x);
		if(it!=S[y].end()) {
			deg[x]-=it->second,S[y].erase(it);
			if(deg[x]==1) Q.push(x);
		}
		if(S[x].size()<S[y].size()) swap(S[x],S[y]);
		for(auto e:S[y]) if(e.second) S[x][e.first]+=e.second;
		dsu[y]=x;
	}
	for(int i=1;i<=n;++i) if(dsu[i]==i) return chk(i)?i:0;
	return 0;
}
int fa[MAXN],L[MAXN],R[MAXN],k,x[MAXN<<1],y[MAXN<<1];
int dep[MAXN],cov[MAXN],del[MAXN];
vector <int> E[MAXN],T[MAXN];
void dfs0(int u) {
	vis[u]=true,L[u]=++dcnt;
	for(int v:G[u]) if(inq[v]) {
		if(!vis[v]) fa[v]=u,dep[v]=dep[u]+1,T[u].push_back(v),dfs0(v);
		else ++k,x[k]=u,y[k]=v,E[v].push_back(u);
	}
	R[u]=dcnt;
}
bool f[MAXN],g[MAXN],rsv[MAXN];
void dfs1(int u) {
	if(cov[u]>0&&f[y[cov[u]]]) f[u]=g[u]=true,rsv[cov[u]]=true;
	for(int v:T[u]) dfs1(v);
}
void dfs2(int u) {
	if(~del[u]) {
		if(del[u]) g[u]|=g[y[del[u]]];
		else g[u]|=(TR.qry(R[u])>TR.qry(L[u]-1));
	}
	if(g[u]) for(int v:E[u]) TR.add(L[v]);
	for(int v:T[u]) dfs2(v);
}
void solve() {
	cin>>n>>m;
	for(int i=1;i<=n;++i) {
		G[i].clear(),E[i].clear(),T[i].clear();
		S[i].clear(),in[i].clear();
		dfn[i]=low[i]=cov[i]=del[i]=deg[i]=0;
		ins[i]=ind[i]=f[i]=g[i]=0;
	}
	dcnt=scnt=tp=0;
	for(int i=1,u,v;i<=m;++i) cin>>u>>v,G[u].push_back(v);
	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
	int id=0;
	for(int i=1;i<=n;++i) for(int j:G[i]) if(col[i]^col[j]) ind[col[j]]=true;
	for(int i=1;i<=scnt;++i) if(!ind[i]) id=(!id?i:-1);
	if(id<=0) {
		for(int i=1;i<=n;++i) cout<<"3"; cout<<"\n";
		return ;
	}
	for(int i=1;i<=n;++i) inq[i]=(col[i]==id);
	int rt=getrt();
	if(!rt) {
		for(int i=1;i<=n;++i) cout<<"32"[inq[i]]; cout<<"\n";
		return ;
	}
	memset(vis,0,sizeof(vis));
	memset(rsv,0,sizeof(rsv));
	dcnt=k=0,dep[rt]=0,dfs0(rt);
	for(int i=1;i<=n;++i) dsu[i]=i;
	for(int e=1;e<=k;++e) {
		for(int u=find(x[e]);dep[u]>dep[y[e]];u=find(fa[u])) {
			if(!cov[u]) cov[u]=e;
			else cov[u]=-1,dsu[u]=find(fa[u]);
		}
	}
	f[rt]=g[rt]=true;
	for(int u:T[rt]) dfs1(u);
	for(int i=1;i<=n;++i) dsu[i]=i;
	for(int e=1;e<=k;++e) if(rsv[e]) {
		for(int u=find(x[e]);dep[u]>dep[y[e]];u=find(fa[u])) {
			if(!del[u]) del[u]=e;
			else del[u]=-1,dsu[u]=find(fa[u]);
		}
	}
	TR.init();
	for(int u:E[rt]) TR.add(L[u]);
	for(int u:T[rt]) dfs2(u);
	for(int i=1;i<=n;++i) {
		if(inq[i]) cout<<"321"[f[i]+g[i]];
		else cout<<"3";
	}
	cout<<"\n";
}
signed main() {
	ios::sync_with_stdio(false);
	int id,cas;
	cin>>id>>cas;
	while(cas--) solve();
	return 0;
}