自动搬运

查看原文

来自洛谷，原作者为

	chzhh_111 退是死，前是生||坐标：FJ，现初三，已学 OI 两年||比赛等级分上不了2000，不改签

搬运于2025-08-24 23:02:46，当前版本为作者最后更新于2024-08-29 14:46:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：

给定一个图，若这个图中的任意两点 $x,y$，存在有从 $x$ 通向 $y$ 的路径或从 $y$ 通向 $x$ 的路径，则就输出 Yes 否则输出 No。

思路 1：

这应该是一种暴力做法。

首先根据题意，一个强连通图肯定合法，因此直接处理出强连通后，构造一个 DAG 就行了，随后再对于这个 DAG 上的每一个节点为起点 BFS 一遍这个 DAG，则所经过的每一个点都与我们的起点所连通。

定义 $vis_{i,j}$ 表示点 $i$ 和点 $j$ 是否联通：如果 $vis_{i,j} = 1$，则点 $i$ 和点 $j$ 联通；如果 $vis_{i,j} = 0$，则点 $i$ 和点 $j$ 不联通。

因此到最后我们只需要枚举 $i$ 和 $j$，如果出现 $vis_{i,j} = 0$ 并且 $vis_{j,i} = 0$ 的情况就输出 No，否则输出 Yes。

代码 1：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+1;
int T,n,m,ls,z[N];bool vis[N][N];
int top,stak[N],dfn[N],low[N],col[N],tot,Time;
queue<int>q;
struct bian{
	int qi,zhong,zhi;
}s[N*6];
void clean()
{
	tot=ls=Time=0;
	memset(z,0,sizeof(z));
	memset(vis,0,sizeof(vis));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(col,0,sizeof(col));
}
void Tarjan(int x)
{
	dfn[x]=low[x]=++Time;
	stak[++top]=x;
	for(int i=z[x];i;i=s[i].zhi)
	{
		int u=s[i].zhong;
		if(!dfn[u])
		{
			Tarjan(u);
			low[x]=min(low[x],low[u]);
		}
		else if(!col[u]) low[x]=min(low[x],low[u]);
	}
	if(dfn[x]==low[x])
	{
		col[x]=++tot;
		while(stak[top]!=x) col[stak[top--]]=tot;
		top--;
	}
}
void bfs(int x)
{
	q.push(x);
	vis[x][x]=1;
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(int i=z[u];i;i=s[i].zhi)
		{
			int v=s[i].zhong;
			vis[x][v]=1;
			q.push(v);
		}
	}
}
void check()
{
	for(int i=1;i<=tot;i++)
	  for(int j=1;j<=tot;j++)
	    if(!vis[i][j]&&!vis[j][i]) {printf("No\n");return;}
	printf("Yes\n");
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		clean();
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			s[++ls]=(bian){u,v,z[u]},z[u]=ls;
		}
		for(int i=1;i<=n;i++)
		  if(!dfn[i]) Tarjan(i);
		int l=ls;
		ls=0;
		memset(z,0,sizeof(z));
		for(int i=1;i<=l;i++)
		{
			int x=col[s[i].qi],y=col[s[i].zhong];
			if(x!=y) s[++ls]=(bian){x,y,z[x]},z[x]=ls;
		}
		for(int i=1;i<=tot;i++)
			bfs(i);
		check();
	}
	return 0;
}

思路 2：

建出 DAG 之后，我们只要考虑这个 DAG 中的最长链的长度是否等于强连通的个数。

因为如果这个 DAG 中的最长链的长度不等于强连通的个数，则就一定存在两个强连通之间不能由其中一个到达另外一个，便不符合题意。

最长链的长度可以用拓扑 DP 求出来，设定 $dp_{i}$ 表示以第 $i$ 个强连通为终点的最长链的长度，则动态转移方程是：$dp_{i}= \max (dp_{j}) + 1$，其中的 $j$ 表示第 $i$ 个强连通的前驱。

代码 2：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+1;
int T,n,m,ls,z[N];
int top,stak[N],dfn[N],low[N],col[N],tot,Time,ru[N],dp[N];
queue<int>q;
struct bian{
	int qi,zhong,zhi;
}s[N*6];
void clean()
{
	tot=ls=Time=0;
	memset(z,0,sizeof(z));
	memset(dp,0,sizeof(dp));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(col,0,sizeof(col));
	memset(ru,0,sizeof(ru));
}
void Tarjan(int x)
{
	dfn[x]=low[x]=++Time;
	stak[++top]=x;
	for(int i=z[x];i;i=s[i].zhi)
	{
		int u=s[i].zhong;
		if(!dfn[u])
		{
			Tarjan(u);
			low[x]=min(low[x],low[u]);
		}
		else if(!col[u]) low[x]=min(low[x],low[u]);
	}
	if(dfn[x]==low[x])
	{
		col[x]=++tot;
		while(stak[top]!=x) col[stak[top--]]=tot;
		top--;
	}
}
void bfs()
{
	int maxi=1;
	for(int i=1;i<=tot;i++) if(!ru[i]) q.push(i),dp[i]=1;
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(int i=z[u];i;i=s[i].zhi)
		{
			int v=s[i].zhong;
			dp[v]=max(dp[v],dp[u]+1);
			maxi=max(maxi,dp[v]);
			if(!(--ru[v])) q.push(v);
		}
	}
	if(maxi==tot) printf("Yes\n");
	  else printf("No\n");
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		clean();
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			s[++ls]=(bian){u,v,z[u]},z[u]=ls;
		}
		for(int i=1;i<=n;i++)
		  if(!dfn[i]) Tarjan(i);
		int l=ls;
		ls=0;
		memset(z,0,sizeof(z));
		for(int i=1;i<=l;i++)
		{
			int x=col[s[i].qi],y=col[s[i].zhong];
			if(x!=y) s[++ls]=(bian){x,y,z[x]},z[x]=ls,ru[y]++;
		}
		bfs();
	}
	return 0;
}