Pat class A - 1013 battle over cities

Link

The question ： Here's a map for you ,n Cities 、m Strip road , Now I ask you after destroying all the roads connected to a city , At least how many roads need to be built to connect all the remaining cities . One k Group test query .

Ideas ： It is equivalent to deleting a point in the connection block and the number of remaining connection blocks -1 The problem of . Ideas 1： Union checking set , Train of thought two ：bfs Traverse . Note the upper limit 1e3 A little bit , So at most 1e6 One side , The capacity is not large enough. The last test point cannot pass .

And look up the set code ：

#include<bits/stdc++.h>
#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 --;  //  When building the edge, we should judge , The number of ancestor nodes cannot be determined in the final traversal 
    }
}

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;
}

dfs Code ：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1005;

int n, m, k, ans;
bool vis[N];
int g[N][N];

void dfs(int x){  // dfs Run all the points you can reach 
    vis[x] = 1;
    for(int i = 1; i <= n; i ++){
        if(!vis[i]&&g[x][i] == 1){
            dfs(i);
        }
    }
}

signed main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i ++){
        int a, b; cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
    while(k--){
        int x; cin >> x;
        memset(vis, 0, sizeof(vis));
        vis[x] = 1; ans = 0;
        for(int i = 1; i <= n; i ++){  //  For each node that has not been visited dfs
            if(!vis[i]){
                dfs(i);
                ans ++;
            }
        }
        cout << ans-1 << endl;
    }

    return 0;
}