首页 > Web开发 > 详细

P1197 [JSOI2008]星球大战(链式前向星 + 逆并查集)

时间:2020-02-28 21:47:06      阅读:53      评论:0      收藏:0      [点我收藏+]

 

https://www.luogu.com.cn/problem/P1197

技术分享图片

 

 

技术分享图片
#include<bits/stdc++.h>

using namespace std;
const int maxn = 4e5 + 5;
int a, b, n, m, k;
int head[maxn], tot, fa[maxn], c[maxn], ans[maxn];
bool pan[maxn];
struct node {
    int next, to;
} edge[maxn];
//链式前向星
void add(int a, int b) {
    edge[tot].to = b;
    edge[tot].next = head[a];
    head[a] = tot++;
}

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int main() {
    // freopen("in", "r", stdin);
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> c[i];
        pan[c[i]] = true;
    }
    for (int i = 0; i < n; i++) {
        if (!pan[i])
            for (int j = head[i]; j >= 0; j = edge[j].next) {
                if (pan[edge[j].to])continue;
                int x = find(i);
                int y = find(edge[j].to);
                fa[x] = y;
            }
    }
    for (int i = 0; i < n; i++)
        if (!pan[i] && find(i) == i)
            ans[k]++;
    for (int i = k - 1; i >= 0; i--) {
        int x = 0;
        pan[c[i]] = false;
        for (int j = head[c[i]]; j >= 0; j = edge[j].next) {
            if (!pan[edge[j].to]) {
                int z = find(c[i]);
                int y = find(edge[j].to);
                if (z != y) {
                    fa[z] = y;
                    x++;
                }
            }
        }
        ans[i] = ans[i + 1] - x + 1;
    }
    for (int i = 0; i <= k; i++)
        cout << ans[i] << endl;
    return 0;
}
View Code

 

P1197 [JSOI2008]星球大战(链式前向星 + 逆并查集)

原文:https://www.cnblogs.com/xcfxcf/p/12378816.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!