0分RE求助呜呜呜
查看原帖
0分RE求助呜呜呜
971468
a13570081961楼主2024/7/28 22:44
// 刷题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include<vector>
#include<set>
using namespace std;
set<int>s;
int n, m;//n个星球,m条路
struct planet {
	bool exit = 1;
	vector<int>father;
	int ancestor;
}p[500000];
int find_anc(int i) {
	int tmp = p[i].ancestor;
	if (tmp != i) {
		p[i].ancestor = find_anc(tmp);
	}
	else {
		return p[i].ancestor;
	}
}
void mergeout(int i1,int i2) {
	int tmp1 = find_anc(i1), tmp2 = find_anc(i2);
	p[tmp1].ancestor = tmp2;
	p[i1].ancestor = tmp2;
}
void merge() {
	for (int i = 0; i < n; i++) {
		if (!p[i].exit)continue;
		p[i].ancestor = i;
	}
	for (int i = 0; i < n; i++) {
		if (!p[i].exit)continue;
		for (int j = 0; j < p[i].father.size(); j++) {
			if (!p[p[i].father[j]].exit)continue;
			mergeout(i, p[i].father[j]);
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		p[i].ancestor = i;
	}
	for (int i = 0; i < m; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		p[tmp1].father.push_back(tmp2);
		p[tmp2].father.push_back(tmp1);
	}
	int acc;
	cin >> acc;
	for (int i = 0; i <= acc; i++) {
		if (i != 0) {
			int tmp;
			cin >> tmp;
			p[tmp].exit = 0;
		}
		merge();

		for (int j = 0; j < n; j++) {
			if (p[j].exit) {
				s.insert(find_anc(j));
			}
		}
		cout << s.size() << endl;
		s.clear();
	}
	return 0;
}
2024/7/28 22:44
加载中...