OpenJudge

E07P01:边的分类

总时间限制:
1000ms
内存限制:
65536kB
描述

给定无权有向图G(V,E),dfs确定每条边的种类。当边(u, v)第一次被遍历,

考虑v的颜色

1.白色,(u,v)为T边,包含在dfs树中

2.灰色,(u,v)为B边,dfs树中子孙指向自己直系祖先的一条边

3.黑色: (u,v)为F边或C边. 此时需要进一步判断

3.1. 若prev[u] < prev[v]:u是v的直系祖先,F边

3.2. 若prev[u] > prev[v]:v早就被发现了, C边



输入
第一行包含两个整数N、M,表示该图共有N个结点和M条有向边。(N <= 5000,M <= 200000)
接下来M行,每行包含2个整数{u,v},表示有一条有向边 u指向v
* 输入顺序保证是字典序
输出
M行,依照输入顺序,每行输出边的u、v、种类
样例输入
5 9
1 2
1 3
1 4
2 3
3 4
3 5
5 1
5 2
5 4
样例输出
1 2 T
1 3 F
1 4 F
2 3 T
3 4 T
3 5 T
5 1 B
5 2 B
5 4 C
提示
* for(int i=1;i<=N;i++)
{
if(prev[i]==-1) dfs(i);
}
全局题号
15261
添加于
2017-07-28
提交次数
30
尝试人数
16
通过人数
15