BZOJ3106/CQOI2013/图的逆变换

Posted on By 二价氢

#题目描述

给一个n结点m条边的有向图D,可以这样构造图E:给D的每条边u->v,在E中建立一个点uv,然后对于D中的两条边u->v和v->w,在E中从uv向vw连一条有向边。E中不含有其他点和边。 输入E,你的任务是判断是否存在相应的D。注意,D可以有重边和自环。

#做法

这不是图论题。

如果存在边uv,且有vb,vc,但uv能连到vb,却不能连到vc,那么显然不合法

枚举u,v,b即可

#复杂度分析 \(O(TN^3)\)

#AC Code