定向

[编程题]定向

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给一张无向图，你需要将边定向，使得定向后的有向图强连通。

输入描述:

第一行两个数n,m，表示点数和边数。
接下来m行，每个两个数x,y，表示x和y之间有条边。

输出描述:

如果不存在可行方案输出一行"impossible" ；

否则，输出一个长度为m的01串，描述你的方案，

第i个字符为1表示输入的第i条边定向为从x到y，为0表示从y到x。

示例1

输入

输出

说明

1->2->3->1，形成一个环 ，是强连通的。

备注:

1 ≤ n,m ≤ 10⁶ ，保证无重边自环

算法知识视频讲解

耕云种月

发表于 2022-07-10 20:33:50

原题解链接：https://ac.nowcoder.com/discuss/149978 dfsd f sdfs 出一棵生成树，令所有树边从父亲指向儿子，所有返祖边从后代指向祖先。判断这样构造的有向图是否强连通即可。正确性证明如下: 如果无向图不连通或者存在割边显然无解，否则这样构造一定是一组展开全文