1013 Battle Over Cities

题目描述

题意理解

题意很简单，给出一张图，问如果去掉其中一个节点以及与这条节点相连的边，需要再添加几条边才能使图重新连通。

解题的关键在于找到要补的边数与图的关系，细想一下马上就知道，对于n个连通分量，使之变成一张连通图需要n-1条边。所以这道题的实质就是求去掉某个节点之后，图中有几个连通分量。

求连通分量的个数有很多方法，dfs、并查集等等，我一开始想到的是并查集，思路是跳过被除掉的节点来建立并查集，最后根的数量减一就是答案，但是却超时了，也想不出优化的办法。

后来就想到dfs，从第一座城市开始深搜，凡是搜到过的城市（也就是联通的城市）都标记为true，再从仍未搜索过的城市开始下一轮深搜，直到所有城市都标记为true，至于被占领的城市一开始就标记为true，这样就可以绕开它了。最后，深搜的次数就是连通分量的个数，再减一就是答案。

代码

首先是能AC的dfs：

#include <bits/stdc++.h>
#define MAXN 1001
using namespace std;

int n, m, k;
int cmap[MAXN][MAXN], visited[MAXN];

void reset(int t)
{
    for (int i = 1; i <= n; i++)
        visited[i] = false;
    visited[t] = true;
}

void dfs(int c, int t)
{
    visited[c] = true;
    for (int i = 1; i <= n; i++)
        if (!visited[i] && cmap[c][i] && i != t)
            dfs(i, t);
}

int solve(int t)
{
    reset(t);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i, t);
            cnt++;
        }
    }
    return cnt - 1;
}

int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int c1, c2; scanf("%d %d", &c1, &c2);
        cmap[c1][c2] = cmap[c2][c1] = 1;
    }
    while (k--) {
        int t; scanf("%d", &t);
        printf("%d", solve(t));
        if (k) printf("\n");
    }
    return 0;
}

最后贴一个并查集（测试样例四超时）：

#include <bits/stdc++.h>
#define MAXN 1001
using namespace std;

int n, m, k;
int cmap[MAXN][MAXN], sset[MAXN];

int find(int ch, int* s)
{
    if (s[ch] == ch) return ch;
    else return find(s[ch], s);
}

void join(int c1, int c2, int* s) 
{
    int fa1 = find(c1, s);
    int fa2 = find(c2, s);
    s[fa1] = fa2;
}

int solve(int t)
{
    for (int i = 1; i <= n; i++) sset[i] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == t || i == j) break;
            if (j == i) continue;
            if (cmap[i][j]) {
                join(j, i, sset);
            }
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (sset[i] == i && i != t)
            cnt++;
    }
    return cnt - 1;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int c1, c2; cin >> c1 >> c2;
        cmap[c1][c2] = cmap[c2][c1] = 1;
        if (c1 > c2) swap(c1, c2);
        join(c1, c2, sset);
    }
    while (k--) {
        int t; cin >> t;
        cout << solve(t);
        if (k) cout << endl;
    }
    return 0;
}