526互联

团体天梯练习 L2-025 分而治之

发布时间 2023-04-19 00:26:32作者: Amαdeus

L2-025 分而治之

分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。

输入格式：

输入在第一行给出两个正整数 \(N\) 和 \(M\)（均不超过 \(10 000\) ），分别为敌方城市个数（于是默认城市从 \(1\) 到 \(N\) 编号）和连接两城市的通路条数。随后 \(M\) 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 \(K\) （ \(≤ 100\) ）和随后的 \(K\) 行方案，每行按以下格式给出：

\(Np\) \(v[1]\) \(v[2]\) ... \(v[Np]\)

其中 \(Np\) 是该方案中计划攻下的城市数量，后面的系列 \(v[i]\) 是计划攻下的城市编号。

输出格式：

对每一套方案，如果可行就输出 \(YES\) ，否则输出 \(NO\) 。

输入样例：

10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2

输出样例：

NO
YES
YES
NO
NO

解题思路

题目大致意思就是一个图中去除了某些点以及点相关的边之后，其余的点是否都度数为0。那么只需要在建图的时候，统计一下度数，然后在每次操作时，标记被删除的点，并处理所有相关联的点的度数。

如果每次处理完之后，存在某个未被删除的点的度数不是0，那么就输出“NO”，否则输出“YES”。

由于需要多次操作，每次操作前都要初始化一下标记数组，并且备份度数。

/*   一切都是命运石之门的选择  El Psy Kongroo  */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, int> psi;
typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
//int dx[4] = {1, -1, 0, 0};
//int dy[4] = {0, 0, 1, -1};
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;

const int N = 10010, M = 2 * N;
int h[N], e[M], ne[M], idx;
int ind[N];    //度数
int backup[N]; //度数备份
bool st[N];    //是否被攻破
int n, m, q;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    ind[b] ++ ;
}

bool solve(){
    memcpy(backup, ind, sizeof(ind)); //度数备份
    memset(st, 0, sizeof(st));        

    int k; cin >> k;
    while(k -- ){
        int u; cin >> u;
        st[u] = true;
        for(int i = h[u]; ~i; i = ne[i]){
            int v = e[i];
            ind[v] -- ;   //所有关联的点度数减1
        }
    }

    bool flag = true;
    for(int i = 1; i <= n; i ++ )
        if(!st[i] && ind[i]){ //既没有被攻破也没有孤立
            flag = false;
            break;
        }
    memcpy(ind, backup, sizeof(backup));  //度数还原
    
    return flag;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    memset(h, -1, sizeof(h));
    while(m -- ){
        int u, v; cin >> u >> v;
        add(u, v), add(v, u);
    }

    cin >> q;
    while(q -- ){
        bool res = solve();
        if(res) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}