PAT 天梯赛 L2-013. 红色警报 【BFS】

题目链接

https://www.patest.cn/contests/gplt/L2-013

思路

可以通过图的连通块个数来判断

假如 一座城市的失去 改变了其他城市之间的连通性

那么 这座城市本来所在的连通块 就会被分裂成为 两个以上的连通块

加上 这座城市 被分裂出来 又多了 一个连通块

所以 在每次失去的时候 我们深搜 判断一下 连通块个数

如果

失去后的连通块个数 > 原来连通块个数 + 1 那么 就要发出红色警报了

要记得 每次更新一下 连通块 个数

每次都要更新

保证每次判断 都是在上一次失去的基础上 判断的

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

const double PI  = 3.14159265358979323846264338327;

const double E   = exp(1);

const double eps = 1e-6;

const int INF  = 0x3f3f3f3f;

const int maxn = 5e2 + 5;

const int MOD  = 1e9 + 7;

int G[maxn][maxn];

int v[maxn];

int n, m;

void dfs(int x)

{

    v[x] = 1;

    for (int i = 0; i < n; i++)

    {

        if (v[i] == 0 && G[x][i] == 1)

            dfs(i);

    }

}

void init()

{

    CLR(G);

    CLR(v);

}

int main()

{

    scanf("%d%d", &n, &m);

    int x, y;

    for (int i = 0; i < m; i++)

    {

        scanf("%d%d", &x, &y);

        G[x][y] = G[y][x] = 1;

    }

    int fin = 0;

    for (int i = 0; i < n; i++)

    {

        if (v[i] == 0)

        {

            dfs(i);

            fin++;

        }

    }

    int k;

    scanf("%d", &k);

    for (int i = 0; i < k; i++)

    {

        scanf("%d", &x);

        for (int j = 0; j < n; j++)

            G[x][j] = G[j][x] = 0;

        int temp = 0;

        CLR(v);

         for (int j = 0; j < n; j++)

         {

            if (v[j] == 0)

            {

                 dfs(j);

                 temp++;

            }

         }

         if (temp > fin + 1)

            printf("Red Alert: City %d is lost!\n", x);

         else

            printf("City %d is lost.\n", x);

         fin = temp;

         if (i == n - 1)

            printf("Game Over.\n");

    }

}