黑书上猴子内个题 逆向思维真是吊
View Code
1 #include <cstdio> 2 #include <cstring> 3 const int N = 500000, M = 500000; 4 int key[M], head[N], next[M], cnt; 5 int a[N], p[N], ans[N]; 6 bool v[N]; 7 inline void add (const int & x, const int & y) 8 { 9 key[cnt] = y; 10 next[cnt] = head[x]; 11 head[x] = cnt ++; 12 } 13 inline int F (int x) { return p[x] == x ? x : p[x] = F (p[x]); } 14 int main () 15 {int n, m;memset (head, -1, sizeof head); 16 scanf ("%d%d", &n, &m); 17 for (int i = 1, a, b; i <= m; i ++) 18 scanf ("%d%d", &a, &b), add (a, b), add (b, a);int k; 19 scanf ("%d", &k); 20 for (int i = 1; i <= k; i ++) 21 scanf ("%d", &a[i]), v[a[i]] = true; 22 for (int i = 1; i <= n; i ++) 23 p[i] = i; 24 int z = n - k; 25 for (int i = 0; i < n; i ++) 26 if (!v[i]) 27 for (int j = head[i]; ~ j; j = next[j]) 28 if (!v[key[j]]) 29 if (F (i) != F (key[j])) 30 p[F (i)] = F (key[j]), z --; 31 ans[k + 1] = z; 32 for (int i = k; i >= 1; i --) 33 { 34 v[a[i]] = false; 35 z ++; 36 for (int j = head[a[i]]; ~ j; j = next[j]) 37 if (!v[key[j]]) 38 if (F (a[i]) != F (key[j])) 39 p[F (a[i])] = F (key[j]), z --; 40 ans[i] = z; 41 } 42 for (int i = 1; i <= k + 1; i ++) 43 printf ("%d\n", ans[i]); 44 return 0; 45 }