现在没有TLE+MLE了,但是还是没办法AC,[现在60。](https://www.luogu.com.cn/record/112508624)
代码:
```cpp
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int n, m, h[N], nodes_count, vis[N];
struct wsnode
{
int next;
int to;
}wsgraph[N];
void add(int x, int y)
{
wsgraph[++nodes_count].next = h[x];
wsgraph[nodes_count].to = y;
h[x] = nodes_count;
}
void dfs(int now, int father)
{
if (vis[now])
{
return;
}
vis[now] = father;
for (int i = h[now]; i; i = wsgraph[i].next)
{
if (!vis[wsgraph[i].to])
{
dfs (wsgraph[i].to, father);
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int u, v;
cin >> u >> v;
add (v, u);
}
memset (vis, 0, sizeof(vis));
for (int i = n; i >= 1; i--)
{
if (vis[i])
{
continue;
}
dfs (i, i);
}
for (int i = 1; i <= n; i++)
{
cout << vis[i] << ' ';
}
cout << endl;
return 0;
}
/*
#include <bits/stdc++.h>
using namespace std;
vector<int> to_node_number[100001];
int n, m;
int vis[100001]; // 记忆化搜索
int A(int x, int depth) // DFS (深度优先搜索)
{
printf ("[wsDbg] [Line 8] [clock %d] vis[%d] = %d, depth = %d, to_node_number[%d].size() = %d\n", clock(), x, vis[x], depth, x, to_node_number[x].size());
if (vis[x] != -1) // 如果已经得到结果
{
return vis[x]; // 直接返回即可
}
int ans = -2147483647;
for (int i = 0; i < to_node_number[x].size(); i++)
{
printf ("[wsDbg] [Line 16] [clock %d] i = %d, ans = %d\n", clock(), i, ans);
ans = max(ans, A(to_node_number[x][i], depth + 1));
}
if (to_node_number[x].size() == 0) // 如果是叶子节点
{
return depth; // 直接返回深度。
}
vis[x] = ans; // 存储得到的结果
printf ("[wsDbg] [Line 24] [clock %d] vis[%d] = %d\n", clock(), x, vis[x]);
return ans;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
to_node_number[u].push_back(v); // 反向建边【暂时禁用】
}
memset (vis, -1, sizeof(vis));
for (int i = 1; i <= n; i++)
{
cout << A(i, 1) << ' ';
}
cout << endl;
return 0;
}
*/
```
by HappyDavid @ 2023-06-11 12:10:26
@[HappyDavid](/user/738761) 史前代码(屎钱代码)
```cpp
#include<bits/stdc++.h>
using namespace std;
struct Link{
int x,y;
}link[100002];
int n,m,f[100002];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>link[i].x>>link[i].y;
for(int i=1;i<=n;i++) f[i]=i;
for(bool find=1;find;){
find=0;
for(int i=1;i<=m;i++)
if(f[link[i].x]<f[link[i].y]){
find=1;
f[link[i].x]=f[link[i].y];
}
}
for(int i=1;i<=n;i++)
cout<<f[i]<<" ";
return 0;
}
```
by Quenna @ 2023-06-11 22:06:15