esquigybcu @ 2021-08-09 21:51:05
qwq
#include <stdio.h>
#include <string.h>
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) printf(__VA_ARGS__)
#endif
const int SIZE = 4e5 + 5, EDGE = 2e5 + 5;
int n, m, k, u, v;
int father[SIZE]; int cur_blocks;
int target[SIZE], blocks[SIZE];
bool present[SIZE];
int get_ancestor(int node)
{
while (node != father[node])
node = father[node] = father[father[node]];
return node;
}
void merge(int a, int b)
{
a = get_ancestor(a);
b = get_ancestor(b);
if (a != b)
cur_blocks--;
father[a] = b;
return;
}
struct edge
{
int u, v, next;
}
e[EDGE];
int head[SIZE];
int cnt = 0;
void add_edge(int u, int v)
{
e[cnt].u = u, e[cnt].v = v, e[cnt].next = head[u];
head[u] = cnt;
cnt++;
}
inline void output_dsu()
{
debug("output_dsu() called\n");
for (int i = 0; i < n; i++)
if (father[i] == i && present[i])
debug("ancestor: %d\n", i);
debug("blocks: %d\n", cur_blocks);
}
int main()
{
scanf("%d %d", &n, &m);
memset(head, -1, sizeof head);
for (int i = 0; i < m; i++)
scanf("%d %d", &u, &v), add_edge(u, v), add_edge(v, u);
memset(present, 1, sizeof present);
scanf("%d", &k);
for (int i = 0; i < k; i++)
scanf("%d", &target[i]), present[target[i]] = 0;
debug("read done\n");
debug("e[] dump: \n");
for (int i = 0; i < cnt; i++)
debug("e[%d]: u = %d, v = %d, next = %d\n", i, e[i].u, e[i].v, e[i].next);
for (int i = 0; i < n; i++)
father[i] = i;
blocks[k] = cur_blocks = n - k;
debug("init done\n");
for (int i = 0; i < m; i++)
if (present[e[i].u] && present[e[i].v])
merge(e[i].u, e[i].v);
debug("merge done\n");
output_dsu();
for (int i = k - 1; i >= 0; i--)
{
debug("i = %d\n", i);
cur_blocks++;
for (int j = head[target[i]]; ~j; j = e[j].next)
if (present[e[j].v])
merge(target[i], e[j].v), debug("j = %d\n", j);
blocks[i] = cur_blocks;
output_dsu();
}
for (int i = 0; i <= k; i++)
printf("%d\n", blocks[i]);
return 0;
}
``
by 已注销GeJD*cy @ 2021-08-09 21:52:39
捕捉 pzq,然后吃掉!
by esquigybcu @ 2021-08-13 22:56:35
wq……e[]
要开两倍大小,然后还要注意有2*m
条边
正在重写/kk
by esquigybcu @ 2021-08-13 23:25:51
此贴终结,我重写了一遍