1013 Battle Over Cities(并查集解法)
关于背景的介绍见1013 Battle Over Cities(图的DFS解法)
DFS就是不算特定结点后数连通子图的总数，再减一。我想着那么并查集就是数不算特定节点后，集合元素(根)的个数。但是我弄错了一件事，我是边输入，边合并，然后对于每一个占领城市的输入，再绕过那座城市，这样是会出问题的，因为被占领城市很可能被算作了根节点。
正确做法是：依然设置一个邻接表，对于每个占领城市的输入，绕开它把其他存在边的结点合并，再数集合元素的个数，最后减一。
AC代码
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
typedef long long LL;using namespace std;const int maxn = 1010;//总城市数上限 int allCityNum,lostIdx;vector<int> G[maxn];int F[maxn];void initF(){for(int i=1;i<=allCityNum;i++)F[i] = i;
} int findSo(int x){int a = x;while(x!=F[x]){x = F[x];}while(a!=F[a]){int z = a;a = F[a];F[z] = x;}return x;
}void unite(int a,int b){int sa = findSo(a);int sb = findSo(b);if(sa!=sb){F[sa] = sb;}
}int main(){int wayNum,lostCityNum;scanf("%d %d %d",&allCityNum,&wayNum,&lostCityNum);for(int i=0;i<wayNum;i++){int ct1,ct2;scanf("%d %d",&ct1,&ct2);G[ct1].push_back(ct2);G[ct2].push_back(ct1);}set<int> roots;for(int i=0;i<lostCityNum;i++){scanf("%d",&lostIdx);initF();roots.clear();for(int j=1;j<=allCityNum;j++){if(j==lostIdx)continue;for(int k=0;k<G[j].size();k++){int u = G[j][k];if(u!=lostIdx)unite(j,u);} }for(int j=1;j<=allCityNum;j++){if(j!=lostIdx){int sj = findSo(j);roots.insert(sj);}}printf("%d
",roots.size()-1);}return 0;
}