P3916 图的遍历(Tarjan缩点和反向建边）

 P3916 图的遍历 - 洛谷 | 计算机科学教育新生态

写法一：Tarjan

思路：先运用Tarjan算法得到每个连通块中最大的编号，然后对每个连通块进行缩点重新建图，进行dfs，得到缩点后的连通块能够达到的最大编号。

Code:

constexpr int N=1e5+5,mod=1e9+7;int a[N],dfn[N],stk[N],low[N],top,scc[N],cnt,tot;
int n,m,instack[N],ma[N],sz[N];
bool st[N];
int x[N],y[N];
vector<int> e[N],g[N];void Tarjan(int u)
{stk[++top]=u,instack[u]=1;low[u]=dfn[u]=++tot;for(auto t:e[u]){if(!dfn[t]){Tarjan(t);low[u]=min(low[u],low[t]);}else if(instack[t]) low[u]=min(low[u],dfn[t]);}if(low[u]==dfn[u]){cnt++; int y;//cout<<"____"<<cnt<<' '<<u<<endl;do{y=stk[top--]; instack[y]=0;scc[y]=cnt;// cout<<"____"<<cnt<<' '<<y<<endl;ma[cnt]=max(ma[cnt],y);}while(u!=y);}
}void dfs(int u)
{if(a[u]) return ;a[u]=ma[u];// cout<<u<<' '<<a[u]<<' '<<g[u].size()<<endl;for(auto t:g[u]){if(!a[t]){dfs(t);}a[u]=max(a[u],a[t]);// cout<<u<<' '<<t<<' '<<a[u]<<endl;}
}
void solve()
{cin>>n>>m;for(int i=0;i<m;i++){cin>>x[i]>>y[i];e[x[i]].push_back(y[i]);}for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);for(int i=0;i<m;i++){if(scc[x[i]]==scc[y[i]]) continue;g[scc[x[i]]].push_back(scc[y[i]]);}for(int i=1;i<=cnt;i++){if(!a[i]) dfs(i);}for(int i=1;i<=n;i++)cout<<a[scc[i]]<<' ';
}

写法二：反向建图

既然要计算每个点能走到的最大编号，我们可以直接从大编号 开始搜索与它关联的路径，该路径上的点均为大编号。

Code:

constexpr int N=1e5+5,mod=1e9+7;int a[N],n,m;
vector<int> e[N];void dfs(int u,int i)
{if(a[u]) return ;a[u]=i;for(auto t:e[u]){if(!a[t]){dfs(t,i);}}}
void solve()
{cin>>n>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;e[b].push_back(a);}for(int i=n;i;i--)if(!a[i]) dfs(i,i);for(int i=1;i<=n;i++) cout<<a[i]<<' ';
}