自动搬运

查看原文

来自洛谷，原作者为

	Lysea Please don't go away.

搬运于2025-08-24 23:17:56，当前版本为作者最后更新于2025-06-19 10:47:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

给你一个图，满足：

若不存在从 $v$ 到 $u$ 的路径，则从 $u$ 到 $v$ 至多只有一条路径。

问每个点可以到达多少个点。

Solution

首先一个强连通分量中的点一定能够互相到达，先缩点。

然后考虑这个性质意味着什么：缩点后，若不存在从 $v$ 到 $u$ 的路径，但从 $u$ 到 $v$ 存在多条路径，则这个图存在“环”。

这里的“环”是不考虑方向的，即将整张图视为无向图的情况下的环。

这也就意味着将整张图视为无向图的情况下，缩点后我们会得到一颗树。

但值得注意，这棵树不一定是内向树或者外向树，它的方向是不定的，所以不能直接找一个根进行 dfs。

但可以考虑记忆化记录每个点能够到达的点的个数，跑多次 dfs，那么这题就做完了。

时间复杂度 $O(n+m)$。

Code

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
using namespace std;
struct star{
	int next,to;
}e[N];
vector<int>vt[N];
bool vis[N];
map<pair<int,int>,bool>mp;
int n,m,dfn[N],low[N],sck[N],fnt,tot,c[N];
int cnt,head[N],qwq,bel[N],in[N],siz[N];
void add(int u,int v){
	e[++cnt].next=head[u];
	head[u]=cnt;
	e[cnt].to=v;
}
void Tarjan(int x){
	dfn[x]=low[x]=++tot;
	sck[++fnt]=x,vis[x]=true;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(!dfn[y]){
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}else if(vis[y]) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		qwq++;
		while(int z=sck[fnt--]){
			vis[z]=false;
			bel[z]=qwq,siz[qwq]++;
			if(x==z) break;
		}
	}
}
void rebuild(){
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=e[j].next){
			int y=e[j].to;
			if(bel[i]==bel[y]||mp[{bel[i],bel[y]}]) continue;
			vt[bel[i]].push_back(bel[y]);
			mp[{bel[i],bel[y]}]=1;
		}
	}
}
int dfs(int x){
	if(c[x]) return c[x];
	c[x]=siz[x];
	for(int v:vt[x]){
		dfs(v);
		c[x]+=c[v];
	}
	return c[x];
}
signed main(){
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) Tarjan(i);
	rebuild();
	for(int i=1;i<=qwq;i++) dfs(i);
	for(int i=1;i<=n;i++) cout<<c[bel[i]]-1<<endl;
	return 0;
}