Problem Specification Value
Time Limit 3 Sec
Memory Limit 162 MB
Submit 4722
Solved 2127

Description

很久以前, 在一个遥远的星系, 一个黑暗的帝国靠着它的超级武器统治者整个星系. 某一天, 凭着一个偶然的机遇, 一支反抗军摧毁了帝国的超级武器, 并攻下了星系中几乎所有的星球. 这些星球通过特殊的以太隧道互相直接或间接地连接. 但好景不长, 很快帝国又重新造出了他的超级武器. 凭借这超级武器的力量, 帝国开始有计划地摧毁反抗军占领的星球. 由于星球的不断被摧毁, 两个星球之间的通讯通道也开始不可靠起来. 现在, 反抗军首领交给你一个任务: 给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序, 以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数. (如果两个星球可以通过现存的以太通道直接或间接地连通, 则这两个星球在同一个连通块中).

Input

输入文件第一行包含两个整数, N (1 <=N <=2M) 和 M (1 <=M <=200, 000), 分别表示星球的数目和以太隧道的数目. 星球用 0~ N-1 的整数编号. 接下来的 M 行, 每行包括两个整数 X, Y, 其中 (0 <=X <> Y 表示星球 x 和星球 y 之间有 “以太” 隧道, 可以直接通讯. 接下来的一行为一个整数 k, 表示将遭受攻击的星球的数目. 接下来的 k 行, 每行有一个整数, 按照顺序列出了帝国军的攻击目标. 这 k 个数互不相同, 且都在 0 到 n-1 的范围内.

Output

输出文件的第一行是开始时星球的连通块个数. 接下来的 N 行, 每行一个整数, 表示经过该次打击后现存星球的连通块个数.

Sample Input

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7

Sample Output

1
1
1
2
3
3

HINT

Source

简单用并查集维护区块连通性就可以解决了~

按照被毁灭的时间倒着进行合并 (如果强制在线我就不知道怎么办了), 然后输出


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 800200, maxm = 800200;

class UnionFindSet
{
public:
    int par[maxn];
    int cnt, n;
    int find(int p)
    {
        if (par[p] == p)
            return p;
        return par[p] = find(par[p]);
    }
    void link(int p, int q)
    {
        // Link p to being a child of q
        p = find(p);
        q = find(q);
        if (p == q)
            return ;
        par[p] = q;
        cnt--;
        return ;
    }
    void build(int _n)
    {
        cnt = n = _n;
        for (int i = 0; i < n; i++)
            par[i] = i;
        return ;
    }
} ufs;

class Graph
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    edge *edges[maxn], epool[maxm];
    int cnt;
    void addedge(int u, int v)
    {
        edge *p = &epool[cnt++],
             *q = &epool[cnt++];
        p->u = u; p->v = v; p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u; q->next = edges[v]; edges[v] = q;
        return ;
    }
    void build(void)
    {
        memset(edges, 0, sizeof(edges));
        return ;
    }
} graph;

int n, m, atk;
int arr[maxn]; // In the order of being attacked
int dest[maxn]; // True if destroyed
int used[maxn]; // True if connected into map
int fres[maxn], rescnt = 0; // The result (to be outputted reversed)

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    graph.build();
    ufs.build(n);
    // Building graph
    for (int i = 1; i <= m; i++) {
        int a = 0, b = 0;
        scanf("%d%d", &a, &b);
        graph.addedge(a, b);
    }
    // Reading attacked planets
    scanf("%d", &atk);
    for (int i = 1; i <= atk; i++) {
        scanf("%d", &arr[i]);
        dest[arr[i]] = true;
    }
    // Connecting all planets after the apocalypse (final status)
    ufs.cnt = 0;
    for (int i = 0; i < n; i++) {
        if (dest[i]) continue;
        ufs.cnt++;
        for (Graph::edge *ep = graph.edges[i]; ep; ep = ep->next)
            if (used[ep->v])
                ufs.link(i, ep->v);
        used[i] = true;
    }
    fres[++rescnt] = ufs.cnt;
    // Connecting them from reversed time sequence
    for (int i = atk; i >= 1; i--) {
        ufs.cnt++;
        for (Graph::edge *ep = graph.edges[arr[i]]; ep; ep = ep->next)
            if (used[ep->v])
                ufs.link(arr[i], ep->v);
        used[arr[i]] = true;
        fres[++rescnt] = ufs.cnt;
    }
    // Output final result
    for (int i = rescnt; i >= 1; i--)
        printf("%d\n", fres[i]);
    return 0;
}

Atom 遇到下划线还是在不停地抽风

from pydatagen import *
m = randrange(3, 2000)
n = randrange((int)(m / 2), m)
printf('%d %d\n' % (n, m))
g = Graph(n, m, connected=False, weighed=False)
print_oi(g)
sz = randrange(1, n)
l = randlist(sz, range(0, n), distinct=True)
printf('%d\n' % sz)
for i in l:
    printf('%d\n' % i)
fclose()