LYDSY 1015

题目大意

暂无

题目解法

暂无

RTFC

#include <cctype>
#include <cstdio>
const int maxn = 500010;
int fa[maxn], to[maxn], next[maxn], head[maxn], ecnt, destroy[maxn], ans, st[maxn], s_top;
bool destroyed[maxn];
inline void readInt(int &x)
{
    int ch = x = 0;
    while (!isdigit(ch = getchar()))
        ;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void link(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy) fa[fx] = fy, ans--;
}
inline void addEdge(int x, int y)
{
    ecnt++;
    to[ecnt] = y;
    next[ecnt] = head[x];
    head[x] = ecnt;
}
int main()
{
    for (int i = 0; i < maxn; i++) fa[i] = i;
    int n, m, k;
    readInt(n), readInt(m);
    for (int i = 0, x, y; i < m; i++)
        readInt(x), readInt(y),
            addEdge(x, y), addEdge(y, x);
    readInt(k);
    for (int i = 0; i < k; i++)
        readInt(destroy[i]), destroyed[destroy[i]] = true;
    ans = n - k;
    for (int i = 0; i < n; i++)
        if (!destroyed[i])
            for (int cur = head[i]; cur; cur = next[cur])
                if (!destroyed[to[cur]])
                    link(i, to[cur]);
    st[s_top++] = ans;
    for (int i = k - 1; i >= 0; i--)
    {
        int x = destroy[i];
        destroyed[x] = false;
        ans++;
        for (int cur = head[x]; cur; cur = next[cur])
            if (!destroyed[to[cur]])
                link(x, to[cur]);
        st[s_top++] = ans;
    }
    while (s_top) printf("%d\n", st[--s_top]);
    return 0;
}