感觉我这个代码能够排除有环的情况,为什么只有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;
}