自动搬运

查看原文

来自洛谷，原作者为

	H2ptimize_AFO 前朝败北者

搬运于2025-08-24 22:43:23，当前版本为作者最后更新于2023-07-12 10:17:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

胡桃敲可爱的~

分析、实现

先贴上 dijkstra 求最短路的代码：

void dijkstra()
{
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
	bool vis[MAXN]={};
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=true;
		for(int i=0;i<G[u].size();i++)
		{
			int v=G[u][i];
			if(dis[v]>dis[u]+1)
			{
				dis[v]=dis[u]+1;
				q.push(make_pair(dis[v],v));
			}
		}
	}
}

与题中的 dfs 对比，很容易发现在 dijkstra 算法中，每当一个结点 $v$ 被进行计算时，它会比较所有的前驱结点，最终留下最优值。

但在 dfs 算法中，一个结点最多只会被计算一次。不难发现，当一个结点有且仅有一个前驱时，dfs 算法才能正确计算最短路。

而此时图实际上是一棵无根树，这个 dfs 算法实际上是用来计算树上结点深度的正解。

所以当且仅当结点 $1$ 所在连通块是一棵树时，才能正确进行最短路计算。否则，一旦结点 $1$ 所在连通块中出现环，环上部分节点计算必然出错。

综上所述，只需要对结点 $1$ 所在连通块检查是否存在环即可。

（其实还有一种简单粗暴的办法，用 dfs 和 dijkstra 各运行一遍，比较答案。）

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e4+10;

int n,m;
bool ans;
vector<int>G[MAXN];

bool vis[MAXN];
void dfs(int u,int fa)//有别于有向图判连通
{
	vis[u]=true;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(v==fa)continue;
		if(!vis[v])dfs(v,u);
		else ans=true;
		if(ans)return;
	}
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ans=false;
		cin>>n>>m;
		for(int i=0;i<=n;i++)
		{
			G[i].clear();
			vis[i]=false;
		}
		for(int i=1;i<=m;i++)
		{
			int u,v;
			cin>>u>>v;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		dfs(1,0);
		if(ans)cout<<"0.000\n";
		else cout<<"1.000\n";
	}
	return 0;
}

胡桃敲可爱的~