使用bfs找最长路,为什么#3#4神奇WA?
查看原帖
使用bfs找最长路,为什么#3#4神奇WA?
308107
Xu__楼主2021/2/23 18:03

如题, 谢谢dalao指出错误!

#include<bits/stdc++.h>
using namespace std;
const long long N = 1e6 + 16;
queue<long long>q;
long long head[N], Next[N], vertex[N], ans, tot, n, m, vis[N], d[N];
void add(long long x, long long y) { vertex[++tot] = y; Next[tot] = head[x]; head[x] = tot; }
void bfs(long long x)
{
	q.push(x);
	vis[x] = 1;
	while (q.size())
	{
		long long u = q.front(); q.pop();
		for (long long k = head[u]; k; k = Next[k])
		{
			long long v = vertex[k];
			if (vis[v]) continue;
			vis[v] = 1; d[v] = d[u] + 1;
			ans = max(ans, d[v]);
			q.push(v);
		}
	}
}
int main()
{
	for (;;)
	{
		cin>>n>>m;
		if (n == 0 && m == 0) break;
		for (long long i = 1; i <= 1000000; i++) d[i] = head[i] = Next[i] = vertex[i] = vis[i] = ans = tot = 0;
		for (long long i = 1, x, y; i <= m; i++) cin>>x>>y, add(x, y), add(y, x);
		for (long long j = 1; j <= n; j++) bfs(j);
		cout<<ans*100<<endl;
	}
	return 0;
}

2021/2/23 18:03
加载中...