摘要
Title: A1013 Battle Over Cities
Tag: 并查集、DFS
Memory Limit: 64 MB
Time Limit: 1000 ms

A1013 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.
思路
- DFS
  一开始思路就是，对除了标记点的点进行DFS，看被分了几个块
- 并查集

代码

DFS

/*
* @Author: NEFU AB-IN
* @Date: 2022-09-03 14:57:08
* @FilePath: \GPLT\A1013\A1013.cpp
* @LastEditTime: 2022-09-03 15:49:12
*/
#include <bits/stdc++.h>
using namespace std;
#define N n + 100
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

signed main()
{
    IOS;
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> g[N], st(N);
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    function<void(int, int)> dfs = [&](int u, int q) {
        for (auto v : g[u])
        {
            if (v == q || st[v])
                continue;
            st[v] = 1;
            dfs(v, q);
        }
    };

    auto check = [&](int q) {
        vector<int>(N).swap(st); // st清0
        int cnt = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (i == q || st[i])
                continue;
            dfs(i, q);
            cnt++;
        }
        return cnt - 1;
    };

    for (int i = 1; i <= k; ++i)
    {
        int q;
        cin >> q;
        cout << check(q) << '\n';
    }
    return 0;
}

并查集

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 500010;

int n, m, k;
int p[N];

struct Edge
{
    int a, b;
}e[M];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 0; i < m; i ++ ) scanf("%d%d", &e[i].a, &e[i].b);

    while (k -- )
    {
        int x;
        scanf("%d", &x);

        for (int i = 1; i <= n; i ++ ) p[i] = i;

        int cnt = n - 1;
        for (int i = 0; i < m; i ++ )
        {
            int a = e[i].a, b = e[i].b;
            if (a != x && b != x)
            {
                int pa = find(a), pb = find(b);
                if (pa != pb)
                {
                    p[pa] = pb;
                    cnt -- ;
                }
            }
        }

        printf("%d\n", cnt - 1);
    }

    return 0;
}

A1013 Battle Over Cities

题意

思路

代码