[AGC071C] Orientable as Desired

· · 题解

或许更好的阅读体验。

思路：

第一眼看上去完全不可做的样子。

那么考虑给 x_i 找一些特殊值，看能不能使得图满足一些特殊的性质；一种显然的想法是先找 x = (0, \cdots, 0)，于是只有对于任意点都满足只有出度或者只有入度的时候，不满足这个 x 的要求。

而显然，任意点都满足只有出度或者只有入度，于是一定可以分成两个部分，左边是只有出度的，右边是只有入度的，然后在两个部分之间有左到右的边，一个部分内部没有边，这显然是一个二分图。

所以，当原图不是二分图的时候，选 x 全 0 就满足要求，输出 Yes 即可；否则原图是二分图，此时全 0 就不合法了，但是多了性质，考虑怎么做？

一样的，如果全 0 不行，那只有一位赋值行不行，这里假设是 x_1 = k，其它是 0，此时把先把和 1 相关的边断开单独处理，那么原图就被分为了若干连通块，显然每个连通块也是个二分图，于是每个连通块存在两种定向方法使得 x_i = 0, i > 1 被满足。

但是加上 1 的边和点了呢，因为原图是二分图，对于每个连通块来说，显然 1 只会和其中一个部分有边，设对于第 i 个连通块，有 p_i 条边，显然，因为两种定向都可以使得 x_i = 0 的条件满足，所以要么 1 全部连向这个连通块，要么这个连通块全部连向 1。

于是假设有 l 个连通块，分别是 p_1, \cdots, p_l，如果 p 中可以选择若干个数使得和为 k 那么 x_1 = k 的条件就会被满足，那么这个 x 就不合法，而 k 是可以取遍 [0, deg_1] 的，所以 p 需要凑出 [0, deg_1] 中的所有数才行。

而 1 是可以任意的，所以当我们只赋值一项 x_u 有值时，x 合法当且仅当这个 u 断开后的 p_1, \cdots, p_l 不能凑出所有的 [0, deg_u]。

继续考虑，如果只有一项有值的时候都无解，那么更多项有值会不会有解呢？假设 x_u = a, x_v = b，把 u, v 断开后形成若干连通块，每个连通块内和 u, v 相关的边分别是 p_1, \cdots, p_l, q_1, \cdots, q_l，你发现还是之前那个问题，要 p 凑出 [0, deg_u]，q 凑出 [0, deg_v]。

之前一项有值时，断一个点都可以凑出 [0, deg_u]，如果 u, v 之间没有边，相当于把之前的 p' 分成更多的 p 了，一样还是可以凑出；否则 u, v 有边的话，还是一样，只是某个下面的某个 p 减少了 1，钦定 u \to v 或者 v \to u 也可以凑出来，

三项或者更多项有值的时候是类似的，设有值的是 S 集合，然后对于 S 内部也是二分图，可以划分成子问题，都可以证明一定可以凑出来；所以只需要判定一项有值的时候是否存在合法的 x 即可。

考虑如何判定，对于一个 u 找到的 p_1, \cdots, p_l，如何凑出 [0, deg_u]？乍一看是背包问题，实际上是贪心问题，因为覆盖的要是一个整数的前缀，先将 p 从小到达排序，设考虑了前 i 个，目前覆盖了 [0, \sum_{j \le i} p_j]（初始 p_0 = 0 开始），想要继续覆盖，显然要满足 \sum_{j \le i} p_j \ge p_{i + 1} - 1，否则中间就有空的凑不出来，此时就可以覆盖 [0, \sum_{j \le i + 1} p_j]。

因为 \sum p_j = deg_u，所以对于所有的 i 都需要满足上面那个条件即可；但是还有一个问题，对于 u 如何快速把它对应的 p 找出来？每次暴力搜连通块是 O(m) 的，而 \sum_u \sum p_i = O(m)，所以只要均摊的找出来就没有问题。

因为是删点，所以考虑 tarjan 求点双的时候在割点那算一下就行了，需要快速判一个边是否存在，用 set 存一下。

时间复杂度为 O(m \log m)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) (x) & (-(x))
#define popcnt(x) __builtin_popcount(x)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
bool flag;
int T, n, m, cnt, top;
int dfn[N], low[N], du[N], stk[N];
bool col[N];
set<int> S[N];
vector<int> E[N], V[N];
inline void add(int u, int v){
    ++du[u], ++du[v];
    E[u].push_back(v);
    E[v].push_back(u);
    S[u].insert(v);
    S[v].insert(u);
}
inline void tarjan(int u){
    dfn[u] = low[u] = ++cnt;
    stk[++top] = u;
    for(auto v : E[u]){
        if(!dfn[v]){
            col[v] = col[u] ^ 1;
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(low[v] == dfn[u]){
                int sum = 0;
                while(1){
                    int x = stk[top--];
                    sum += S[u].count(x);
                    if(x == v)
                      break;
                }
                V[u].push_back(sum);
                du[u] -= sum;
            }
        }
        else{
            low[u] = min(low[u], dfn[v]);
            if(col[u] ^ col[v] ^ 1)
              flag = 1;
        }
    }
}
inline bool check(vector<int> V){
    sort(V.begin(), V.end());
    int sum = 0;
    for(auto v : V){
        if(sum >= v - 1)
          sum += v;
        else
          return 1;
    }
    return 0;
}
inline void solve(){
    cnt = top = flag = 0;
    n = read(), m = read();
    for(int i = 1; i <= n; ++i){
        dfn[i] = low[i] = du[i] = col[i] = 0;
        S[i].clear(), E[i].clear(), V[i].clear();
    }
    while(m--){
        int u = read(), v = read();
        add(u, v);
    }
    tarjan(1);
    if(flag){
        puts("Yes");
        return ;
    }
    for(int u = 1; u <= n; ++u){
        if(du[u])
          V[u].push_back(du[u]);
        if(check(V[u])){
            puts("Yes");
            return ;
        }
        // cerr << "now: " << u << '\n';
        // for(auto v : V[u])
        //   cerr << v << ' ';
        // cerr << '\n';
    }
    puts("No");
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}