求助!第七个点WA了!请求大佬们帮助
查看原帖
求助!第七个点WA了!请求大佬们帮助
389982
LiuzihanAC楼主2021/3/14 14:17
#include<iostream>
using namespace std;

const int N = 1005;

int enemy[1005][1005];

int nenemy[1005];

int cnt, m = 0;

struct node {
	int parent;
	int count;
	int value;
}set[N];

int Find(int x) {      //寻找父亲节点
	int y = x;
	while (set[y].parent != y) {
		y = set[y].parent;
	}
	while (x != y) {   //压缩路径
		int temp = set[x].parent;
		set[x].parent = y;
		x = temp;
	}
	return y;
}

void compress(int cnt) {     //合并后进行路径压缩
	for (int i = 1; i <= cnt; i++) {
		Find(i);
	}
}

void Union(int x, int y) {
	x = Find(x);	   //寻找各自父亲节点
	y = Find(y);
	if (x == y) {
		return;
	}
	if (set[x].count > set[y].count) {   //启发式搜索,使树的高度小一些
		set[y].parent = x;
		set[x].count += set[y].count;
	}
	else {
		set[x].parent = y;
		set[y].count += set[x].count;
	}
}

void Init(int cnt) {
	for (int i = 1; i <= cnt; i++) {
		set[i].count = 1;
		set[i].parent = i;
		set[i].value = 0;
	}
}

int CountGroup(int cnt) {
	int ans = 0;
	for (int i = 1; i <= cnt; i++) {
		set[Find(i)].value = 100;
	}
	for (int i = 1; i <= cnt; i++) {
		if (set[i].value == 100) {
			ans++;
		}
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> cnt >> m;
	Init(cnt);
	for (int i = 1; i <= m; i++) {
		char s;
		int x, y = 0;
		cin >> s;
		cin >> x >> y;
		if (s == 'F') {
			Union(x, y);
		}
		else {
			enemy[x][++nenemy[x]] = y;
			enemy[y][++nenemy[y]] = x;
		}
	}
	for (int i = 1; i <= cnt; i++) {
		if (nenemy[i] >= 2) {
			for (int t = 1; t <= nenemy[i]; t++) {
				for (int j = i + 1; j <= nenemy[i]; j++) {
					Union(enemy[i][t], enemy[i][j]);
				}
			}
		}
	}
	cout << CountGroup(cnt);
	return 0;
}

我的答案是26而标准答案是25. 请问大佬们该怎么改?

2021/3/14 14:17
加载中...