bzoj 1015[JSOI2008]星球大战starwar - 并查集

 ?1 #include <iostream> ?2 #include <cstdio> ?3 #include <cstring> ?4 #include <algorithm> ?5 #define LL long long ??6 ??7 using namespace std; ?8 ??9 const int MAXM = 2e5 + 10; 10 const int MAXN = 4e5 + 10; 11 int N, M, K; 12 int cnt = 0; 13 int ans[MAXN]; 14 int exs[MAXN]; 15 int x, y; 16 int father[MAXN]; 17 int head[MAXN]; 18 ?19 int find(int x) 20 { 21 ????if(x != father[x]) { 22 ????????father[x] = find(father[x]); 23 ????} 24 ????return father[x]; 25 } 26 struct edge { 27 ????int use; 28 ????int v; 29 ????int next; 30 } g[MAXM * 3]; 31 ?32 void addedge(int u, int v) 33 { 34 ????g[cnt].v = v; 35 ????g[cnt].use = 0; 36 ????g[cnt].next = head[u]; 37 ????head[u] = cnt++; 38 } 39 int d[MAXN]; 40 inline LL read() 41 { 42 ????LL x = 0, w = 1; char ch = 0; 43 ????while(ch < ‘0‘ || ch > ‘9‘) { 44 ????????if(ch == ‘-‘) { 45 ????????????w = -1; 46 ????????} 47 ????????ch = getchar(); 48 ????} 49 ????while(ch >= ‘0‘ && ch <= ‘9‘) { 50 ????????x = x * 10 + ch - ‘0‘; 51 ????????ch = getchar(); 52 ????} 53 ????return x * w; 54 } 55 ?56 void init() 57 { 58 ????memset(head, -1, sizeof head); 59 ????for(int i = 0; i < N; i++) { 60 ????????father[i] = i; 61 ????} 62 } 63 int main() 64 { 65 ????N = read(), M = read(); 66 ????init(); 67 ????for(int i = 1; i <= M; i++) { 68 ????????int u = read(), v = read(); 69 ????????addedge(u, v); 70 ????????addedge(v, u); 71 ????} 72 ????K = read(); 73 ????for(int i = 1; i <= K; i++) { 74 ????????int k = read(); 75 ????????d[i] = k; 76 ????????exs[k] = 1; 77 ????} 78 ????ans[K + 1] = N - K; 79 /* ???for(int i = 0; i < N; i++) { 80 ????????cout<<exs[i]<<" "; 81 ????} 82 ????cout<<endl; 83 ????cout<<find(2)<<" "<<find(6)<<endl;*/ 84 ????for(int i = 0; i < N; i++) { 85 ????????if(!exs[i]) { 86 ????????????for(int j = head[i]; j != -1; j = g[j].next) { 87 ????????????????int to = g[j].v; 88 ????????????????if(!g[j ^ 1].use && !exs[to]) { 89 ????????????????????g[j].use = 1; 90 ????????????????????x = find(to), y = find(i); 91 ????????????????????if(x != y) { 92 ????????????????????????father[y] = x; 93 ????????????????????????ans[K + 1]--; 94 ????????????????????} 95 ????????????????} 96 ????????????} 97 ????????} 98 ????} 99 ????for(int i = K; i >= 1; i--) {100 ????????int k = d[i];101 ????????ans[i] = ans[i + 1] + 1;102 ????????for(int j = head[k]; j != -1; j = g[j].next) {103 ????????????int to = g[j].v;104 ????????????if(!exs[to] && !g[j ^ 1].use) {105 ????????????????g[j].use = 1;106 ????????????????x = find(to), y = find(k);107 ????????????????if(x != y) {108 ????????????????????father[y] = x;109 ????????????????????ans[i]--;110 ????????????????}111 ????????????}112 ????????}113 ????????exs[k] = 0;114 ????}115 ????for(int i = 1; i <= K + 1; i++) {116 ????????printf("%d\n", ans[i]);117 ????}118 ????return 0;119 }120 121 /*122 8 13123 0 1124 1 6125 6 5126 5 0127 0 6128 1 2129 2 3130 3 4131 4 5132 7 1133 7 2134 7 6135 3 6136 5137 1138 6139 3140 5141 7142 143 144 */