[BFS] CF653E. Bear and Forgotten Tree 2

E. Bear and Forgotten Tree 2

题意：bear有一颗n个节点的树，现在他忘了这个树的结构，只知道有m条边不可能存在，还记得1号节点的出度是k，问可不可能存在这样一棵满足条件的树。

题解：首先保证1号点的出度要大于等于 k，然后去掉1号节点，看其他点的连通性，求出连通块缩点，然后试着用1号节点去连接这些连通块，显然当连通块的数量大于k的时候就是无解。还有种情况就是某一连通块的所有点都不可能和1连边，那么也肯定是无解的，在bfs时可以顺便判断出。满足以上条件时，便是n个节点构成的连通图，通过再次拆边肯定可以构造出树，所以找图就够了。写法上要用set维护当前的缩点情况，否则会超时。

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const int N = 300005;
int n, m, k;
set<int>G[N];
set<int>tar; // tar维护当前的缩点
bool vis[N] = {0};
int bfs(int s){
    queue<int>q;
    q.push(s); vis[s] = 1;
    vector<int>tmp;
    tmp.clear();
    int flag = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(auto v: tar){
            if(v != u && !G[u].count(v) && !vis[v]){
                vis[v] = 1;
                tmp.push_back(v);
                q.push(v);
            }
        }
        if(!G[u].count(1)) flag = 1; // 判断是否当前块所有点都不能和1连边
        for(auto i: tmp) tar.erase(i); // 缩点，删去和s相连的点，只留下s
        tmp.clear();
    }
    return !flag;
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 2; i <= n; ++i) tar.insert(i); // 初始所有点都是非连通的
    int dg = n-1; // 1号点的出度
    for(int i = 0; i < m; ++i){
        int a, b;
        scanf("%d%d", &a, &b);
        G[a].insert(b);
        G[b].insert(a);
        if(a == 1 || b == 1) dg -= 1;
    }
    if(dg < k){ puts("impossible"); return 0; } // 1号点的出度小于k，无解
    for(int i = 2; i <= n; ++i){
        if(!vis[i] && tar.count(i)){
            if(bfs(i) == 1){ // 某一连通块不能和1连边，无解
                puts("impossible");
                return 0;
            }
        }
    }
    if(tar.size() > k) puts("impossible"); // 连通块的数量大于k，无解
    else puts("possible");
}