BlackJulySnow#Note#2018-10-24星球大战1

--- title: 2018-10-24星球大战 tags: 逆向思维,并查集 grammar_cjkRuby: true --- ```cpp #include #include #include using namespace std; const int MAXI=4e5+4; int f[MAXI],head[MAXI],h[MAXI],ans[MAXI],En=0;//f为并查集，h为打击点存储的数组，ans为每次打击后的答案 bool e[MAXI]; //e来判断是否被打击掉 int find(int x) { if(x!=f[x]) f[x]=find(f[x]); //并查集基本函数 return f[x]; } struct edge { int from; int to; //定义一个结构体来存储邻接表 int next; }a[MAXI]; void insert(int u,int v) { //邻接表存储数据 a[En].from=u; a[En].next=head[u]; a[En].to=v; head[u]=En; En++; } int main() { int n,m,k,x,y,tot,i,u; cin>>n>>m; for(i=0;i>x>>y; insert(x,y);insert(y,x); //双向存储数据 } cin>>k; tot=n-k; //打击k次后所剩下的点 for(i=1;i<=k;i++) { cin>>x; e[x]=true; //被打击掉后就true，并把打击的点存储到h中 h[i]=x; } for(i=0;i<2*m;i++) {