NOI2024 树形图 graphee
Rainbow_qwq
·
·
题解
D2T3 树形图
首先判掉一些 case：先 tarjan 一遍求出强连通分量，找到一个能到达所有点的强连通分量（也可能找不到），那么 1,2 类点只可能在这个强连通分量中。
若其中没有 1 类点，则强连通分量内所有点都为 2 类点。
### 求出 $1$ 类点
以任意一个 $1$ 类点定为根，求出一棵 dfs 树。考虑在这棵 dfs 树的基础上求出所有 $1$ 类点：
考虑 $fa_u\to u$ 这条边被几条返祖边覆盖了，由于这是一个强连通分量，所以子树中至少有一条返祖边覆盖 $fa_u\to u$。
若有 $\ge 2$ 条返祖边覆盖了 $fa_u\to u$，则 $u\to fa_u$ 有至少两种方案能走到，$u$ 必然不为 $1$ 类点。
若只有 $1$ 条返祖边覆盖了 $fa_u\to u$，设这条边为 $x\to y$，则 $u$ 子树中的点向上走必然要走到 $y$，$u$ 是否为 $1$ 类点等价于 $y$ 是否为 $1$ 类点。于是可以从上到下递推出所有 $1$ 类点。
### 求出 $2$ 类点
仍然在这棵 dfs 树的基础上求出 $2$ 类点。
如果一个 $u$ 为 $1$ 类点，那么一定有恰好一条返祖边 $x\to y$ 覆盖了 $fa_u\to u$，并且这条返祖边**不能删除**，否则 $x$ 的子树就会脱离这个强连通分量，从而不再是 $1$ 类点。
于是我们得到了若干条返祖边不能删除的限制。
假设我们想判定 $u$，也就是删去若干条边把 $u$ 变为 $1$ 类点，则我们想删去覆盖了 $fa_u\to u$ 的若干条返祖边，使得只剩下一条 $(x,y)$ 覆盖了 $fa_u\to u$，并且 $y$ 也是 $1/2$ 类点，那么 $u$ 就可以成为 $2$ 类点了。
对于一个点 $u$，仍然考虑 $u\to fa_u$ 这条边：
若被两条不能删除的返祖边覆盖，则 $u$ 一定不可行。
若被一条不能删除的返祖边覆盖：设这条边为 $x\to y$，则 $u$ 是否为 $2$ 类点等价于 $y$ 是否为 $1/2$ 类点。
若被零条不能删除的返祖边覆盖：那么 $u$ 子树中有若干条**能删除**的返祖边。若能找到一条能删除的返祖边 $x\to y$，使得 $y$ 为 $1/2$ 类点，则 $u$ 就可以为 $2$ 类点。
### 如何找一个 $1$ 类点
考虑以 $1$ 类点为根构成的 dfs 树的性质。观察其叶子，由于没有横叉边，所有叶子必然满足入度为 $1$。
对于所有入度为 $1$ 的点 $u$，假设有边 $v\to u$，则可以把 $u$ 向 $v$ 合并。具体来说，把 $u$ 的出边并到 $v$ 的出边里（所有 $u\to x$ 改为 $v\to x$，**不需要去除重边**，但要删去自环），然后删除点 $u$。也就是在 dfs 树上不断缩叶子的过程。
BFS 不断执行这个过程，并把新出现的入度为 $1$ 的点加入队列里。
在若干轮删除之后，若只剩下 $1$ 个点，则这个点即可作为 $1$ 类点；否则若某个时刻每个点入度都 $\ge 2$，则不存在 $1$ 类点。
使用启发式合并维护边集，时间复杂度 $O((n+m)\log n)$。
可以用 vector 存下每个点的入边和出边，合并时按两个 size 的和加权，取更小的点的所有边合并到大的点上，这样在合并时就可以计算有多少条 $u-v$ 的边。
```cpp
// what is matter? never mind.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 200005
#define inf 0x3f3f3f3f
int n,m,rt;
bool res1[maxn],res2[maxn];
int dfn[maxn],low[maxn],idx,scc,st[maxn],tp,bel[maxn];
vi e[maxn],ps[maxn];
void tar(int u){
dfn[u]=low[u]=++idx;
st[++tp]=u;
for(int v:e[u]){
if(!dfn[v])tar(v),low[u]=min(low[u],low[v]);
else if(!bel[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]!=low[u])return;
int v; ++scc; do{
v=st[tp--];
bel[v]=scc;
ps[scc].pb(v);
} while(u!=v);
}
int q[maxn],hd,tl;
bool vis[maxn];
bool bfs(int u){
For(i,1,n)vis[i]=0;
q[hd=tl=1]=u; vis[u]=1;
For(i,1,tl){
int x=q[i];
for(int y:e[x])if(!vis[y])vis[y]=1,q[++tl]=y;
}
For(i,1,n)if(!vis[i])return 0;
return 1;
}
struct ufs{
int fa[maxn];
void init(int n){
For(i,0,n) fa[i]=i;
}
int gf(int x){
while(x!=fa[x])x=fa[x]=fa[fa[x]];
return x;
}
void mg(int u,int v){
fa[gf(u)]=gf(v);
}
bool chk(int u,int v){
return gf(u)==gf(v);
}
}U[2];
namespace fd{
vi e[maxn],re[maxn];
int deg[maxn];
int cnt,eu[maxn],ev[maxn];
void init(){
For(i,1,n)e[i].clear(),re[i].clear(),deg[i]=0;
cnt=0;
}
void adde(int u,int v){
++deg[v];
++cnt,eu[cnt]=u,ev[cnt]=v;
e[u].pb(cnt),re[v].pb(cnt);
}
ufs U;
bool chk(int u,int v,int x,int y){
return (u==x&&v==y)||(u==y&&v==x);
}
void merge(int u,int v){
deg[v]+=deg[u];
if(SZ(re[u])+SZ(e[u])>SZ(re[v])+SZ(e[v])){
for(auto &i:e[v]) if(chk(U.gf(eu[i]),U.gf(ev[i]),u,v)) --deg[v];
for(auto &i:re[v])if(chk(U.gf(eu[i]),U.gf(ev[i]),u,v)) --deg[v];
swap(re[u],re[v]);
swap(e[u],e[v]);
}else{
for(auto &i:e[u]) if(chk(U.gf(eu[i]),U.gf(ev[i]),u,v)) --deg[v];
for(auto &i:re[u])if(chk(U.gf(eu[i]),U.gf(ev[i]),u,v)) --deg[v];
}
for(auto &x:e[u]) e[v].pb(x);
for(auto &x:re[u])re[v].pb(x);
U.fa[u]=v;
e[u].clear(),re[u].clear(),deg[u]=0;
if(deg[v]<=1) q[++tl]=v;
}
int find(){
hd=1,tl=0;
For(i,1,n)if(deg[i]<=1)q[++tl]=i;
U.init(n);
For(i,1,tl){
int u=q[i];
if(U.gf(u)==u && deg[u]==1){
int to=0,id=0;
for(int i:re[u])
if(U.gf(eu[i])!=U.gf(u))
to=U.gf(eu[i]),id=i;
re[u].clear();
re[u].pb(id);
merge(u,to);
}
}
return U.gf(1);
}
}
int fa[maxn],dep[maxn];
vi e1[maxn],e2[maxn];
void dfs1(int u){
dfn[u]=low[u]=++idx;
vis[u]=1;
for(int v:e[u]){
if(bel[v]!=bel[u])continue;
if(!dfn[v]) fa[v]=u,dep[v]=dep[u]+1,dfs1(v),low[u]=min(low[u],low[v]),e1[u].pb(v);
else if(vis[v]) low[u]=min(low[u],dfn[v]),e2[u].pb(v);
}
vis[u]=0;
}
vi up[maxn],bak[maxn];
int cnt,eu[maxn],ev[maxn],bad[maxn];
void dfs2(int u){
for(auto v:e2[u]){
int i=++cnt;
eu[i]=u,ev[i]=v;
bad[i]=0;
up[u].pb(i);
bak[v].pb(i);
}
for(auto v:e1[u]){
dfs2(v);
for(auto t:up[v]) up[u].pb(t);
}
sort(ALL(up[u]),[&](int x,int y){
return dep[ev[x]]<dep[ev[y]];
});
while(SZ(up[u]) && (SZ(up[u])>2 || dep[ev[up[u].back()]]>=dep[u])) up[u].pop_back();
}
int cc[maxn];
void dfs3(int u){
if(u!=rt){
if(SZ(up[u])==1){
int z=up[u][0];
res1[u]=res1[ev[z]];
if(res1[u] && !bad[z]){
bad[z]=1;
cc[eu[z]]+=1;
cc[ev[z]]-=1;
}
}
else res1[u]=0;
}
for(auto v:e1[u]) dfs3(v),cc[u]+=cc[v];
}
void dfs4(int u){
if(res2[u]){
for(auto i:bak[u]){
int v=eu[i];
int w=bad[i];
for(int p=U[w].gf(v);dep[p]>dep[u];p=U[w].gf(p)){
if(cc[p]==w) res2[p]=1;
U[w].fa[p]=fa[p];
}
}
}
for(auto v:e1[u]) dfs4(v);
}
bool ok=0;
void dfs0(int u){
if(!ok)return;
++cc[u];
if(cc[u]>1)return ok=0,void();
vis[u]=1;
for(int v:e[u])if(!vis[v])dfs0(v);
vis[u]=0;
}
bool chk1(int u){
For(i,1,n)cc[i]=0,vis[i]=0;
ok=1;
dfs0(u);
if(!ok)return 0;
For(i,1,n)if(cc[i]!=1)return 0;
return 1;
}
void work(int O)
{
n=read(),m=read();
For(i,1,n)e[i].clear(),ps[i].clear(),dfn[i]=bel[i]=low[i]=0,res1[i]=res2[i]=0; idx=scc=tp=0; fd::init();
For(i,1,m){
int u=read(),v=read();
e[u].pb(v);
fd::adde(u,v);
}
For(i,1,n)if(!dfn[i])tar(i);
if(!bfs(ps[scc][0])){
For(i,1,n)cout<<'3';cout<<'\n';
return;
}
For(i,0,1)U[i].init(n);
//rt=0;
//For(i,1,n)if(chk1(i))rt=i;
//cout<<"rt "<<rt<<endl;
rt=fd::find();
if(!chk1(rt))rt=0;
if(!rt){
For(i,1,n){
if(bel[i]==scc)cout<<'2';
else cout<<'3';
}cout<<'\n';
return;
}
For(i,1,n){
e1[i].clear(),e2[i].clear(),up[i].clear(),bak[i].clear();
cc[i]=0;
dfn[i]=vis[i]=fa[i]=dep[i]=0;
}cnt=0;idx=0,scc=0;
res1[rt]=1;
dfs1(rt);
dfs2(rt);
dfs3(rt);
For(i,1,n)res2[i]=res1[i];
dfs4(rt);
For(i,1,n){
if(res1[i])cout<<'1';
else if(res2[i])cout<<'2';
else cout<<'3';
}
cout<<'\n';
}
signed main()
{
int T=1;
read();T=read();
For(_,1,T)work(_);
return 0;
}
/*
*/
```