本文共 1846 字，大约阅读时间需要 6 分钟。

题意就是求每个点最多被多少个点传递到

那么直接上缩点,反向建图变成一个$DAG$

然后每个点有自己的点权,可以从入度为$0$的开始$dfs$

累加点权.另外拓扑排序是不可行的。

#include 
   
    using namespace std;const int maxn = 3e5+10;int t,n,m,casenum=0;int in[maxn],f[maxn],w[maxn];vector
    
     vec[maxn];int scc[maxn],sccn,stac[maxn],dfn[maxn],low[maxn],vis[maxn],top,id;struct edge{
   	int u,to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
   	d[++cnt] = (edge){
   u,v,head[u]},head[u] = cnt; }void tarjan(int u){
   	low[u] = dfn[u] = ++id, stac[++top] = u, vis[u] = 1;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( !dfn[v] )			{
   			tarjan( v );			low[u] = min( low[u],low[v] );		}		else if( vis[v] )			low[u] = min( low[u],dfn[v] );	}	if( dfn[u]==low[u] )	{
   		++sccn; int temp;		while( temp = stac[top--] )		{
   			w[sccn]++;//点数			scc[temp] = sccn, vis[temp] = 0; 			if( temp==u )	break;		}	}}int sdf=0;void dfs(int u){
   	for(auto v:vec[u] )	{
   		if( vis[v] )	continue;		vis[v] = 1; dfs(v);		sdf += w[v];	}}void init(){
   	id = sccn = top = 0; cnt = 1;	for(int i=0;i<=n;i++)	{
   		dfn[i]=low[i]=head[i]=w[i]=in[i]=f[i]=scc[i]=0;		vec[i].clear();	}}int main(){
   	cin >> t;	while( t-- )	{
   		cin >> n >> m;		for(int i=1;i<=m;i++)		{
   			int l,r; scanf("%d%d",&l,&r);			add(l+1,r+1); 		}		for(int i=1;i<=n;i++)			if( !dfn[i] )	tarjan(i);		for(int i=2;i<=cnt;i++)		{
   			int u = d[i].u, v = d[i].to;			if( scc[u]==scc[v] )	continue;			vec[scc[v]].push_back( scc[u] );			in[scc[u]]++;		}		int ans = 0;		for(int i=1;i<=sccn;i++)			if( !in[i] )			{
   				dfs(i),f[i]=sdf+w[i]-1,sdf=0;				ans = max( ans,f[i] );				for(int j=1;j<=sccn;j++)	vis[j] = 0;			}		int flag = 0;		printf("Case %d: %d\n",++casenum,ans);		for(int i=1;i<=n;i++)			if( f[scc[i]]==ans )			{
   				if( flag )	printf(" ");				printf("%d",i-1);				flag = 1;			}		printf("\n");		init();	}}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110039037 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！