PAT1013 Battle Over Cities

分析：
思路一：题目要求是给定你一个图，要求判断删除图中的一个点后，联通分量的个数。
开始的思路是用并查集，每次删除一个点后，查询集合中不同的集合数，然后减2即可。
思路二：换个角度想，题目就是求解联通分量的个数，直接dfs即可。

开始没有std::ios::sync_with_stdio，造成了超时，最后一个测试点一直过不去。 或者换成scanf就可以过了。

DFS

#include<bits/stdc++.h>
#define maxn 1100
using namespace std;
int vis[maxn],mp[maxn][maxn];
int cnt,q,n,m,k;
void dfs(int x){
    vis[x]=1;for(int i=1;i<=n;i++){
    if(!vis[i]&&mp[x][i]==1){
    dfs(i);}}
}
int main(){
    std::ios::sync_with_stdio(false);cin>>n>>m>>k;for(int i=0;i<m;i++){
    int x,y;cin>>x>>y;mp[x][y]=1;mp[y][x]=1;}for(int i=0;i<k;i++){
    memset(vis,0,sizeof(vis));cnt=0;cin>>q;vis[q]=1;   //该点被攻占了，不能访问for(int j=1;j<=n;j++){
    if(!vis[j]){
    dfs(j);cnt++;}}cnt--;cout<<cnt<<endl;}return 0;
}

并查集

#include<bits/stdc++.h>
#define maxn 1100
using namespace std;
int n,m,k;
int pa[maxn],mp[maxn][maxn];
typedef struct Node{
    int s,e;
}node;
node e[maxn*maxn];
int findSet(int x){
    if(x!=pa[x]) pa[x]=findSet(pa[x]);return pa[x];
}
void unionSet(int x,int y){
    x=findSet(x);y=findSet(y);if(x==y) return ;pa[x]=y;
}
void solve(int x){
    for(int i=1;i<maxn;i++){
    pa[i]=i;}for(int i=0;i<m;i++){
    if(e[i].s==x||e[i].e==x) continue;unionSet(e[i].s,e[i].e);}int ans=0;for(int i=1;i<=n;i++){
    if(pa[i]==i) {
    ans++;}}ans=ans-2;cout<<ans<<endl;
}
int main(){
    std::ios::sync_with_stdio(false);memset(pa,0,sizeof(pa));cin>>n>>m>>k;for(int i=0;i<m;i++){
    cin>>e[i].s>>e[i].e;}int q;for(int i=0;i<k;i++){
    cin>>q;solve(q);}return 0;
}