1013 Battle Over Cities(1)

图的不连通块计数——遍历图

题面

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 city​1​​-city​2​​ and city​1​​-city​3​​. Then if city​1​​ is occupied by the enemy, we must have 1 highway repaired, that is the highway city​2​​-city​3​​.

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

本题的任务是去数一个图中不连通块的个数,难度不是很大。我在做的时候第一个想到的是在遍历图的时候辅助以vis数组来计数,下面是代码:

// 邻接矩阵宽搜
#include <cstdio>
#include <iostream>
#include <queue>
#define MAXN 1000
using namespace std;
bool ori[MAXN][MAXN];
int n, m, k;

int count(int d)
{
    bool vis[MAXN];
    fill(vis, vis + n, 0);
    int ans = 0;
    queue<int> q; // 宽搜,不多解释
    for (int i = 0; i < n; i++)
    {
        if (!vis[i] && i != d) // 枚举每个点,保证每个点都访问一遍且不重复访问
        {
            // cout << "\nempty\n";
            vis[i] = true;
            q.push(i);
            ans++;

            while (!q.empty()) // 将与这个点连通的点都访问一边
            {
                int c = q.front();
                // cout << i << "out\n";
                q.pop();
                for (int j = 0; j < n; j++)
                {
                    if (ori[c][j] && j != d && !vis[j])
                    {
                        vis[j] = true; // 注意!要在加入队列的时候就改变vis数组的值(而非从队列取出的时候),否则会重复加入而超时
                        q.push(j);
                        // cout << i << "in\n";
                    }
                }
            }
            // 如果跳出while,说明与这个点连通的点都被访问过。
            // 接下来如果再访问的话,访问的点就属于另一个不连通的块
        }
    }

    return ans;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int f, t;
        cin >> f >> t;
        ori[f - 1][t - 1] = true;
        ori[t - 1][f - 1] = true;
    }
    for (int i = 0; i < n; i++)
    {
        ori[i][i] = true;
    }

    for (int i = 0; i < k; i++)
    {
        int concern;
        cin >> concern;
        if (i != 0)
        {
            cout << '\n';
        }
        cout << count(concern - 1) - 1; // (如果不考虑不连通块个数为零的情况下)需要建立的边的个数等于不连通块的个数减一
    }
    return 0;
}

绝大部分情况下,邻接表的性能会比邻接矩阵更为优秀,因此我们再尝试使用邻接表过一下这题,基本逻辑和上面的方法一样(邻接表:使用vector直接记录每个点的邻接点,使用push_back方法加入):

// 邻接表+宽搜
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#define MAXN 1000
using namespace std;
vector<int> ori[MAXN];
int n, m, k;

int count(int d)
{
    bool vis[MAXN];
    fill(vis, vis + n, 0);
    int ans = 0;
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        if (!vis[i] && i != d)
        {
            // cout << "\nempty\n";
            vis[i] = true;
            q.push(i);
            ans++;

            while (!q.empty())
            {
                int c = q.front();
                // cout << i << "out\n";
                q.pop();
                for (int j = 0; j < ori[c].size(); j++)
                {

                    if (ori[c][j] != d && !vis[ori[c][j]])
                    {
                        vis[ori[c][j]] = true;
                        q.push(ori[c][j]);
                        // cout << i << "\n";
                    }
                }
            }
        }
    }

    return ans;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int f, t;
        cin >> f >> t;
        ori[f - 1].push_back(t - 1);
        ori[t - 1].push_back(f - 1);
    }

    for (int i = 0; i < k; i++)
    {
        int concern;
        cin >> concern;
        if (i != 0)
        {
            cout << '\n';
        }
        cout << count(concern - 1) - 1;
    }
    return 0;
}

经过oj测评,发现邻接表确实比邻接矩阵快(一点点?)

其实这题还可以用并查集做,详见下一篇博客,还没写,我先去吃饭。

btw,感谢bzb奆佬深夜帮我看奇怪超时代码,十分感谢。

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments