小埋学习图之环问题WA60求救

常规
1

小埋学习图之环问题 - 题目详情 - 信友队 (xinyoudui.com)
dfs

#include <bits/stdc++.h>
using namespace std;

vector <int> g[1005];
int n, m, vis[1005], t, minn = 1e9;

void dfs(int x, int c)
{
	if (vis[x])
	{
		if (x == t && c != 1)
		{
			minn = min(minn, c);
		}
		return;
	}
	vis[x] = 1;
	for(int i = 0; i < g[x].size(); i++)
	{
		int nx = g[x][i];
		dfs(nx, c + 1);
	}
	return;
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i = 1; i <= n; i++)
	{
		t = i;
		memset(vis, 0, sizeof(vis));
		dfs(t, 1);
	}
	if (minn != (int)(1e9))
	{
		cout << minn;
	}
	else
	{
		cout << -1;
	}
	return 0;
}
2 个赞
2

题目截图发出来，我没权限

2 个赞
3

时间：1s 空间：512M

题目描述：

小埋最近在学习图相关知识，平时做的一些题目都是没有环的情况，现在小埋遇到了一个关于图的环的问题，

问题描述是有一个含n个顶点的双向图，每对顶点最多通过一条边连接，让小埋找到图中的最短的环的长度，

如果不存在环的话，就输出-1。

环是指以同一节点开始和结束，并且路径中的每条边仅使用一次。

题目输入：

第一行是两个整数n，m，n代表该图有n个节点，m的话代表有m条双向边。

题目输出：

输出一个整数是该图中的最小环的长度。

2 个赞
4

这个你保证了吗

2 个赞
5

image
image1141×757 37.5 KB

2 个赞
6

你这没有保证啊

2 个赞
7

输入

4 4
1 2
2 3
3 4
1 4

建出来的图应该是

image
image661×463 6.04 KB

答案是 4 你输出 3

2 个赞
8

然而你因为没有保证只经过一次，造成了答案错误。

2 个赞
9

咋全都是小埋，我非常好奇（呵呵

3 个赞
10

现在WA80

#include <bits/stdc++.h>
using namespace std;

struct node
{
	int x, p;
};

vector <int> g[1005];
queue <node> q;
int vis[1005], dis[1005];
int t, n, m, minn = 1e9;

void bfs()
{
	memset(vis, 0, sizeof(vis));
	memset(dis, 0, sizeof(dis));
	vis[t] = t;
	dis[t] = 0;
	while (q.size())
	{
		q.pop();
	}
	q.push({t, 0});
	while (q.size())
	{
		int x = q.front().x, p = q.front().p;
		q.pop();
		for(int i = 0; i < g[x].size(); i++)
		{
			int nx = g[x][i];
			dis[nx] = dis[x] + 1;
			if (vis[nx] == 0)
			{
				vis[nx] = t;
				q.push({nx, x});
			}
			else
			{
				if (nx != p)
				{
					minn = min(minn, dis[x] + dis[nx]);
					return;
				}
			}
		}
	}
	return;
}
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i = 1; i <= n; i++)
	{
		t = i;
		bfs();
	}
	if (minn != (int)(1e9))
	{
		cout << minn;
	}
	else
	{
		cout << -1;
	}
	return 0;
}
2 个赞
11

额，都是一个老师出的呗，大部分老师都习惯用同一个角色来出题

3 个赞
12

这是干啥的

2 个赞
13

你可以对你之前的 dfs 优化一下，每条边标个号然后判断有没有已经经过那条边

2 个赞
14

判断是否是上一个点
是就说明当前这条走了两次
（改该输出-1的输出了其他数）

2 个赞
15

我真的不能理解你 nx != p 干啥的

2 个赞
16

p是前一个点

2 个赞
17

有 hack 数据吗

2 个赞
18

？

2 个赞
19

变50了:roll_eyes:

2 个赞
20

你能下载下来一个 80 分的数据吗

2 个赞