UOJ134 【UR #9】App 管理器题解

题意：

iOS 用户和 Android 用户一定对 App 管理器不会陌生。

“啊啊啊！手机空间又不够了” 买了低端机的 cxy 欲哭无泪。

cxy 常有的文件格式一共有 \(n\) 种，分别编号为 \(1, \cdots, n\)。 cxy 有 \(m\) 个 App，分别编号为 \(1, \cdots, m\)。其中 \(i\) 号 App 可以把 \(a_i\) 号文件格式转换成 \(b_i\) 号文件格式，或者把 \(b_i\) 号文件格式转换成 \(a_i\) 号文件格式。

App 管理器最近推出了一个新功能：卸载一半！于是 cxy 决定把每个 App 都卸载一半。

对于 \(i\) 号 App，你可以决定你卸载哪一半：

把 \(a_i\) 号文件格式转换成 \(b_i\) 号文件格式。

把 \(b_i\) 号文件格式转换成 \(a_i\) 号文件格式。

cxy 希望，把所有 App 都卸载一半之后并不影响使用。即，对于任意两个文件格式 \(i, j\)，仍能通过一个或多个 App 把 \(i\) 号文件格式直接或间接转换成 \(j\) 号文件格式。

现在 cxy 已经把部分 App 卸载一半了，请你给出一组卸载剩下的 App 的方案满足条件。

省流：一个混合图，把里面的无向边都定向，使得定向之后的图强连通，求一个方案。

输入格式：

第一行两个整数 \(n, m\)，表示文件格式的数量和 App 的数量。保证 \(n \geq 1, m \geq 0\)。

接下来 \(m\) 行，每行三个整数 \(a_i, b_i, t_i\)，表示一个 App。

如果 \(t_i = 0\) 则表示这个 App 还没被卸载一半，如果 \(t_i = 1\) 则表示这个 App 已经被卸载一半，现在只能把 \(a_i\) 号格式转换为 \(b_i\) 号格式。

保证 \(1 \leq a_i, b_i \leq n\) 且 \(a_i \neq b_i\)。

输出格式：

输出 \(m\) 行，每行一个整数表示卸载的是哪一半。

如果这个 App 还没被卸载一半，输出 0 表示保留 “把 \(a_i\) 号文件格式转换成 \(b_i\) 号文件格式” 的这一半，否则表示保留 “把 \(b_i\) 号文件格式转换成 \(a_i\) 号文件格式” 的这一半。

如果这个 App 已经被卸载一半，那么直接输出 0。

保证至少存在一组方案。

数据范围：

\(n,m \le 5000\) 。

首先考虑全为无向边的情况我们如何对其定向。

显然这个图一定为边双连通图，否则无论怎么定向都不行，而题目保证有解。

我们直接对这个图 dfs ，然后把树边都定为父亲到儿子的方向，返祖边都定到祖先的方向。

可以证明这样的图一定是强连通的。如果不是，那么必定存在一个点，

它在 dfs 树的后代中，没有返祖边连向这个点的祖先，那么原图就不是双连通图了，矛盾。

然后考虑混合图的情况。显然这个图一开始就是强连通的状态。

考虑一条无向边 \((u,v)\)

如果从 \(u\) 到 \(v\) 存在一条不经过这条边的路径，那么我们可以把这条无向边定向成 \(v \to u\) 。
如果从 \(v\) 到 \(u\) 存在一条不经过这条边的路径，那么我们可以把这条无向边定向成 \(u \to v\) 。

假设这两种情况都不满足，不妨设从 \(u\) 不经过这条边能到达的节点集合 \(S\) 。

由于原图强连通，则 \(v\) 也可以不经过 \(u\) 到达 \(T = V \setminus S\) 里的点

对于 \(S\) 里的任何可以到达 \(v\) 的节点，例如某个点 \(s\) 到 \(v\) 不用经过 \(u\) ，

则 \(u \leadsto s \leadsto v\) 就是一个不经过那条边的路径，这与假设矛盾。

所以 \(S\) 里的任何点都可以不经过 \(v\) 到 \(u\) ，同理 \(T\) 里的点到 \(v\) 都不用经过 \(u\) 。

考虑 \(S\) 和 \(T\) 之间的边，除了 \((u,v)\) 外一定还有一条边（双联通）。

不妨假设这条边是从 \(S\) 中的 \(p\) 到 \(T\) 中的 \(q\) ，则 \(u \leadsto p \to q \leadsto v\) 就是一条不经过 \((u,v)\) 的路径，与假设矛盾。

因此，上述的两种情况必然会出现一种。

我们只需要一次考虑每条边，然后 dfs 出符合哪种情况并定向即可

时间复杂度 \(\mathcal{O}(m^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e3 + 15))
#define addEdge(u, v) e[u].push_back(v)

int dfn, u[N], v[N], t[N], vis[N];
list<int> e[N]; list<int>::iterator i1[N], i2[N];
void dfs(int x)
{
    vis[x] = dfn;
    for(int y : e[x]) if(vis[y] != dfn) dfs(y);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> t[i];
        if(t[i]) addEdge(u[i], v[i]);
        else {
            addEdge(u[i], v[i]); --(i1[i] = e[u[i]].end());
            addEdge(v[i], u[i]); --(i2[i] = e[v[i]].end());
        }
    }
    for(int i = 1, j; i <= m; i++)
        if(t[i]) cout << "0\n";
        else {
            e[u[i]].erase(i1[i]); e[v[i]].erase(i2[i]);
            ++dfn; dfs(v[i]); j = (vis[u[i]] != dfn);
            cout << char('0' | j) << '\n';
            j ? addEdge(v[i], u[i]) : addEdge(u[i], v[i]);
        }
    return 0;
}