为什么正向建图是错的?
查看原帖
为什么正向建图是错的?
1107543
yezhufenglv楼主2025/6/28 14:43

感觉我这个代码能够排除有环的情况,为什么只有40分

#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[2 * N], ne[2 * N], idx;
int n, m;
int mx[N];
bool used[N];
void connect(int be, int fi)
{
	ne[idx] = h[be];
	e[idx] = fi;
	h[be] = idx++;
}

int dfs(int x)
{
	mx[x] = x; /*避免有环*/
	for (int i = h[x]; i != -1; i = ne[i])
	{
		int next = e[i];
		if (mx[next] == 0) /*避免有环*/
		{
  			dfs(next);
		}
		mx[x] = max(mx[x], mx[next]);
	}
	return mx[x];
}
int main()
{
	memset(h, -1, sizeof h);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int be, fi; cin >> be >> fi;
		connect(be, fi);
	}
	for (int i = 1; i <= n; i++)
	{
		if (mx[i] ==0)
		{
			dfs(i);
		}
	}
	for (int i = 1; i <= n; i++)
		cout << mx[i] << ' ';
	return 0;

}


2025/6/28 14:43
加载中...