PAT 1013 Battle Over Cities

1013 Battle Over Cities

It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities connected. Given the map of cities which have all the remaining highways marked, you are supposed to tell the number of highways need to be repaired, quickly.

For example, if we have 3 cities and 2 highways connecting city1​-city2​ and city1​-city3​. Then if city1​ is occupied by the enemy, we must have 1 highway repaired, that is the highway city2​-city3​.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 3 numbers N (<1000), M and K, which are the total number of cities, the number of remaining highways, and the number of cities to be checked, respectively. Then M lines follow, each describes a highway by 2 integers, which are the numbers of the cities the highway connects. The cities are numbered from 1 to N. Finally there is a line containing K numbers, which represent the cities we concern.

Output Specification:

For each of the K cities, output in a line the number of highways need to be repaired if that city is lost.

Sample Input:

3 2 3
1 2
1 3
1 2 3

Sample Output:

1
0
0

代码：

看大佬的代码写的，既然想不到的话，那就好好多谢斜题目吧！

#include 
#include 
using namespace std;
 
const int N=1010;
bool st[N];
int g[N][N];
int n,m,k;
 
void dfs(int t){
    st[t]=true;
    
    for(int i=1;i<=n;i++)
        if(!st[i] && g[t][i]==1)    dfs(i);
}
 
int main(){
    cin >> n >> m >> k;
    
    //使用邻接矩阵存储两个城市之间是否有通路
    for(int i=0;i
        int a,b;
        scanf("%d%d",&a,&b);
        g[a][b]=g[b][a]=1;
    }
    
    for(int i=0;i
        memset(st,false,sizeof st);//每一次更新所有的点都是未被访问过的
        int t,cot=0;
        scanf("%d",&t);
        st[t]=true;//只要把当前点置为true，表明这个点已经访问过了，其他点与这个点相连的路线都已经不能使用了
        for(int j=1;j<=n;j++){
            if(st[j]==false){//dfs的作用是把当前点连同的地方都打上标记，表示这个点与当前点连通，直到递归结束，这样与当前点连通的点都已经被访问过了
                dfs(j);
                cot++;
            }
        }
        printf("%d\n",cot-1);
    }
    
    return 0;
}

并查集：

#include
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e6+10;
 
int n, m, k, ans;
int f[N];
 
int find(int x){
    return f[x]==x ? x : f[x]=find(f[x]);
}
 
void join(int x, int y){
    int a = find(x), b = find(y);
    if(a != b){//判断两个点是否是在同一个集合当中，如果不是则加入，并不是判断重边
        f[a] = b;
        ans --;  
    }
}
 
struct node{
    int a, b;
} g[N];
 
signed main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i ++){
        cin >> g[i].a >> g[i].b;
    }
 
    while(k--){
        int x; cin >> x;
        for(int j = 1; j <= n; j ++) f[j] = j;
        ans = n-1;
        for(int j = 1; j <= m; j ++){
            if(g[j].a==x||g[j].b==x) continue;
            join(g[j].a, g[j].b);//如果当前两个点都不是被占据的点，说明当前边不与被占领城市相连，则将两个加入一个集合中
//            cout << "a: " << g[j].a << " b: " << g[j].b << endl;
        }
        cout << ans-1 << endl;
    }
 
 
    return 0;
}

 好好学习，天天向上！

我要考研！