GPLT L2-025. 分而治之

题目链接戳这里
题意是:给你一副无向图,问去掉一些点之后,剩下的点是否都孤立.若都孤立则输出"YES", 否则"NO"

一开始想着从点的角度入手然后建立邻接表..然后每一次询问先把表给拷贝下来不要被破坏,再把所有关于被删点的边去掉,统计连通数...好复杂..然后看了这个博客

这里的思路是:我们只记录下边,然后设所有点都没访问过,即vis[i]=0,每去掉一个点v,就vis[v]=1.最后遍历所有的边,是否每条边都残缺不全,即其中1个或2个端点被vis=1了. 如果不是,则证明有点不孤立,输出"NO"

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define fi first
#define se second
typedef pair<int, int> nd;
const int inf = 0x3f3f3f3f, maxN = 1e5 + 5;
int N, M, vis[maxN];
nd E[maxN];

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d %d", &N, &M);
    rep(i, 0, M) {
        int a, b;
        scanf("%d %d", &a, &b);
        E[i].fi = a;
        E[i].se = b;
    }
    int K;
    scanf("%d", &K);
    while (K--) {
        int u, v;
        scanf("%d", &u);
        mst(vis, 0);
        rep(i, 0, u) {
            scanf("%d", &v);
            vis[v] = 1;
        }
        int ok = 1;
        rep(i, 0, M) {
            if (vis[E[i].fi] || vis[E[i].se])
                continue;
            ok = 0;
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}