Edge Split

Created by LXC on Tue Mar 19 19:08:19 2024

https://codeforces.com/problemset/problem/1726/D

ranting: 2000

tag: brute force, constructive algorithms, dfs and similar, dsu, graphs, probabilities, trees

problem

给定一个含有 $n$ 个点 $m$ 条边的无向简单图。

对这张简单图的所有边进行红蓝染色。其中仅由红边组成的无向图连通块数为 $c_1$，仅由蓝边组成的无向图连通块数为 $c_2$。

请构造一种染色方案使得 $c_1 + c_2$ 最小。如果有多种构造方案，任意输出一种即可。

输入格式

第一行包含一个整数 $T ; (1 \leqslant T \leqslant 10^5)$ 表示测试样例组数。

对于每组测试样例，第一行包含两个整数 $n ; (2 \leqslant n \leqslant 2 \cdot 10^5 )$ 和 $m ; (n - 1 \leqslant m \leqslant \min(n + 2, \frac{n \cdot (n - 1)}{2}))$ 表示该简单图的点数和边数。

接下来的 m 行，含有两个数 $u_i$ 和 $v_i ; (1 \leqslant u_i,v_i \leqslant n, ; u_i \neq v_i)$ 表示点 $u_i$ 和点 $v_i$ 间存在一条有向边。数据满足图联通且不存在重边和自环。

数据满足 $\sum n \leqslant 10^6, ; \sum m \leqslant 2 \cdot 10^6$

输出格式

对于每组测试样例，包含一行一个长度为 $m$ 的 $01$串 $s$ 表示其中一种满足题目条件的染色方案。其中 $s_i = 0$ 表示边 $(u_i, v_i)$ 被染成的红色，否则表示被染成了蓝色。

$Translated ; by ; Zigh$

solution

设$k = m-(n-1)$

考虑全部将边染为红色，那么此时$c_1 = 1, c_2 = n$

选择一条在红环上的边染为蓝色，则$c_1 = 1, c_2 = n-1$

我们最多可以找出k条红环上的边，最后红色的边组成了一颗生成树。再移除红色边则$c_1>1$。

也就是说可以让$c_1 = 1, c_2 = n-k$，此时$c_1+c_2 = 2n-m$是最小值。

但是注意到k最多为3，当三条蓝色边成环，则有n-2个连通块，并不是n-3。

所以我的算法就是，先用红色边生成树，剩余的边涂成蓝色，如果蓝色边不是3条，那么直接输出答案。否则需要让一条蓝色边变为红色边，然后在红环上寻找另一个原生的红边变为蓝边。

我选择再次用并查集，在将一条蓝边变为红边，并跳过剩余两条蓝边的情况下，生成树。便可以找到另一条不成环的蓝边。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n, m;
    cin >> n >> m;
    string s(m, '1');
    vector<int> fa(n+1, -1);
    function<int(int)> ufind = [&](int x) {
        return fa[x] < 0 ? x: fa[x] = ufind(fa[x]);
    };
    vector<vector<pair<int,int>>> g(n+1);
    vector<pair<int,int>> e;
    for (int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        e.emplace_back(x, y);
        g[x].emplace_back(y, i);
        g[y].emplace_back(x, i);
        int fx = ufind(x), fy = ufind(y);
        if (fx != fy) {
            fa[fx] = fy;
        } else {
            s[i] = '0';
        }
    }
    if (m-n+1 < 3){
        cout << s << "\n";
        return ;
    }
    // cout << s << endl;
    map<int,int> mp;
    for (int i=0; i<m; i++) {
        if (s[i] == '0') {
            auto [x, y] = e[i];
            // cout << i << " " << x << " " << y << endl;
            mp[x]++;
            mp[y]++;
        }
    }
    // cout << mp << endl;
    int ok = 0;
    for (auto [x,y]:mp) {
        if (y != 2) ok = 1;
    }
    if (!ok) {
        int p = 0;
        while (s[p] == '1') p++;
        // cout << p << endl;
        s[p] = '1';
        for (int& i:fa) i = -1;
        auto [x,y] = e[p];
        fa[x] = y;
        for (int i=0; i<m; i++) {
            if (i == p) continue;
            auto [x, y] = e[i];
            int fx = ufind(x), fy = ufind(y);
            if (fx != fy && s[i] != '0') {
                fa[fx] = fy;
            } else {
                s[i] = '0';
            }
        }
    }
    cout << s << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}