萌新求助本地MLE
查看原帖
萌新求助本地MLE
242543
Ryo_Yamada楼主2020/5/16 18:36

闰土,并查集判最小环,本地挂掉了,交上去MLE+WA,可能又犯sb错误了

#define IOI return//这个不要管
#define AK 0
#define BMY ;

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 200005;
int n, fa[N], dis[N], mn = 0x7fffffff, t;

void init() { for(int i = 1; i <= n; i++) fa[i] = i; }

int find(int x) {
	if(fa[x] != x) {
		t = fa[x];
		fa[x] = find(fa[x]);
		dis[x] = dis[t] + 1;
	}
	return x;
}

void merge(int x, int y) {
	int tx = x, ty = y;
	x = find(x), y = find(y);
	if(x != y) fa[x] = y, dis[tx] = dis[ty] + 1;
	else mn = min(mn, dis[ty] + 1);
}

int main() {
	cin >> n;
	init();
	for(int i = 1; i <= n; i++) {
		int j;
		scanf("%d", &j);
		//cout << "OK\n"; 
		merge(i, j);
	}
	cout << mn << endl;	
	IOI AK BMY
}
2020/5/16 18:36
加载中...