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;
}