0分RE求助呜呜呜

P1197 [JSOI2008] 星球大战

a13570081961 @ 2024-07-28 22:44: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;
}

|