记录编号	577672	评测结果	AAAAAAAAAAAAAAAAAAAEAAAAAAAAAAAAA
题目名称	[POI 2012]Salaries	最终得分	96
用户昵称	HeSn	是否通过	未通过
代码语言	C++	运行时间	5.437 s
提交时间	2022-11-20 16:47:42	内存使用	51.51 MiB

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
int n, w[MAXN], f[MAXN], fa[MAXN], maxn[MAXN], pos[MAXN], cnt[MAXN];
vector<int> cd[MAXN];
int find(int x) {
	if(x == fa[x]) {
		return x;
	}
	return fa[x] = find(fa[x]);
}
void dfs(int x) {
	if(!maxn[x]) {
        maxn[x] = find(maxn[f[x]] - 1);
        pos[maxn[x]] = x;
        cnt[maxn[x]] ++;
    }
	for(int i = 0; i < cd[x].size(); i ++) {
		int u = cd[x][i];
		dfs(u);
	}
}
signed main() {
	freopen("salaries.in", "r", stdin);
	freopen("salaries.out", "w", stdout);
	cin >> n;
	if(n == 1) {
		cout << 1;
		return 0;
	}
	for(int i = 1; i <= n; i ++) {
		fa[i] = i;
	}
	for(int i = 1; i <= n; i ++) {
		scanf("%d%d", &f[i], &w[i]);
		maxn[i] = w[i];
		if(f[i] != i) {
			cd[f[i]].push_back(i);
		}
		fa[w[i]] = w[i] - 1;
	}
	for(int i = 1; i <= n; i ++) {
		if(f[i] == i) {
			dfs(i);
		}
	}
	int sum = 0;
	for(int i = 1; i <= n; i ++) {
        if(fa[i] == i) {
        	sum ++;
		}
        if(cnt[i] && sum == 1) {
        	w[pos[i]] = i;
		}
        sum -= cnt[i];
    }
    for(int i = 1; i <= n; i ++) {
    	printf("%d\n", w[i]);
	}
	return 0;
}