奸笑熊常有的文件格式一共有 $n$ 种，分别编号为 $1, \cdots, n$。奸笑熊有 $m$ 个 App，分别编号为 $1, \cdots, m$。其中 $i$ 号 App 可以把 $a_i$ 号文件格式转换成 $b_i$ 号文件格式，或者把 $b_i$ 号文件格式转换成 $a_i$ 号文件格式。
App 管理器最近推出了一个新功能：卸载一半！于是奸笑熊决定把每个 App 都卸载一半。
对于 $i$ 号 App，你可以决定你卸载哪一半：
奸笑熊希望，把所有 App 都卸载一半之后并不影响使用。即，对于任意两个文件格式 $i, j$，仍能通过一个或多个 App 把 $i$ 号文件格式直接或间接转换成 $j$ 号文件格式。
现在奸笑熊已经把部分 App 卸载一半了，请你给出一组卸载剩下的 App 的方案满足条件。
第一行两个非负整数 $n, m$ ($1 \leq n \leq 5000; 0 \leq m \leq 5000$)，表示文件格式的数量和 App 的数量。
接下来 $m$ 行，每行三个整数 $a_i, b_i, t_i$ ($1 \leq a_i, b_i \leq n; a_i \neq b_i; t_i \in \{0, 1\}$)，表示一个 App。如果 $t_i = 0$ 则表示这个 App 还没被卸载一半，如果 $t_i = 1$ 则表示这个 App 已经被卸载一半，现在只能把 $a_i$ 号格式转换为 $b_i$ 号格式。
输出 $m$ 行，每行一个整数表示卸载的是哪一半。
如果这个 App 还没被卸载一半，输出 $0$ 表示保留 "把 $a_i$ 号文件格式转换成 $b_i$ 号文件格式" 的这一半，否则表示保留 "把 $b_i$ 号文件格式转换成 $a_i$ 号文件格式" 的这一半。
如果这个 App 已经被卸载一半，那么直接输出 $0$。
保证至少存在一组方案。
注意到题目中，"保证至少存在一组方案"，因此存在一种对该图的定向方案，使得该图强连通。
首先有一个性质，强连通图的基图 (注：基图指的是将有向图所有的有向边替换为无向边后得到的无向图) 一定是个边双连通图。
证明很简单，考虑换为无向图后的一条边 $(u, v)$，不妨设原来在有向图的边为 $u \to v$，由于原图是强连通图，故存在从 $v$ 到 $u$ 的有向路径，因此 (在无向图中) 删掉 $(u, v)$ 后 $u, v$ 仍然连通。
然而题中给出的图是有向无向边都有的混合图，注意到题目保证有解，因此容易发现将原图看成有向图 (即将无向边看成两条有向边) 后是强连通的。(因为强连通图加入若干条边还是强连通的)
我们考虑一条未定向的无向边 $(u, v)$。如果能将它定向，且依然还满足上述红色性质。那么由数学归纳法 (对定向的边数进行归纳) 就可以对所有的无向边进行定向，从而得到一个解。当然，蓝色性质是一直都满足的，我们在归纳的过程中需要用到。
对这条无向边 $(u, v)$。我们先将它去掉。如果去掉后的图依然存在从 $v$ 到 $u$ 的路径，那么我们可以将这条边定向为 $u \to v$，从而还是满足上面的红色性质的。
反之，若存在从 $u$ 到 $v$ 的路径，则可以将它定向为 $v \to u$，这样还是满足上述性质。
那如果两种情况都没出现呢？
我们证明在红色性质和蓝色性质下，这种情况不可能出现。
使用反证法。设删掉这条边后，不存在 $u$ 到 $v$ 的路径，也不存在 $v$ 到 $u$ 的路径。那么设 $u$ 所能到达的点的集合为 $S$，从 $v$ 所能到达的点的集合为 $T$，则 $u \in S; u \notin T; v \in T; v \notin S$。
考虑 $s \in S$，由红色性质，存在 $s$ 到 $u$ 的路径。由 $S$ 的定义，这条路径上的所有点都在 $S$ 中。
所以 $S$ 是一个强连通分量，同理 $T$ 也是一个强连通分量。
若 $S \cap T \neq \varnothing$，设 $w \in S \cap T$，则 $u \leadsto w \leadsto v$ 是从 $u$ 到 $v$ 的一条路径，矛盾。所以 $S \cap T = \varnothing$。
若 $S \cup T \neq V$ ($V$ 为原图点集)，设 $w \in V \setminus \left( S \cup T \right)$，则由红色性质，存在 $u$ 到 $w$ 的路径。若不经过 $(u, v)$，则存在 $u$ 到 $w$ 不经过 $(u, v)$ 的路径，从而 $w \in S$。若经过 $(u, v)$，则存在 $v$ 到 $w$ 不经过 $(u, v)$ 的路径，从而 $w \in T$，矛盾。故 $S \cup T = V$。
故 $S, T$ 是原点集的一个 $2-$划分。那么，除了 $(u, v)$ 外，不应该存在跨越 $S$ 和 $T$ 集合的有向或无向边。
于是 $(u, v)$ 为原图基图的桥边，与蓝色性质矛盾。
因此上面二者必居其一。因此我们可以一步一步对每条边归纳而保持这两个性质成立，最终就能得到一组合法解啦。
时间复杂度为 $O \left( m^2 \right)$。
#include <bits/stdc++.h>
#define N 5005
#define addedge(u, v) e[u].push_back(v)
typedef std::list <int> List;
int V, E;
int u[N], v[N], t[N];
int dfn = 0, tag[N];
List e[N];
List::iterator i1[N], i2[N];
void dfs(int x) {
tag[x] = dfn;
for (int y : e[x])
if (tag[y] != dfn) dfs(y);
}
int main() {
int i, j;
scanf("%d%d", &V, &E);
for (i = 1; i <= E; ++i) {
scanf("%d%d%d", 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 (i = 1; i <= E; ++i, putchar(10))
if (t[i]) putchar(48);
else {
e[u[i]].erase(i1[i]); e[v[i]].erase(i2[i]);
++dfn; dfs(v[i]); j = tag[u[i]] != dfn;
putchar(48 | j);
j ? addedge(v[i], u[i]) : addedge(u[i], v[i]);
}
return 0;
}
坑1：注意实现过程中会有删边操作，因此可以考虑用双向链表或 std::list 存边。