#P254. 染色
染色
给定一个n个点m条边的有向图,起初每个点都是白色。
现在需要将所有点都染成黑色,染色规则如下:
每次染色可以选出任意多的点,并将它们染成黑色,但必须满足:这组点中不存在一对点,使得从其中一点出发可以沿若干条有向边走到另一个点。
你需要求出至少几次染色才能将所有点染成黑色。
【输入格式】
第一行两个正整数n,m。
接下来m行每行两个正整数a,b,表示一条从a连向b的单向边。
【输出格式】
一行,一个整数,表示最少的染色次数。
【样例输入1】
5 4
1 2
2 3
3 1
4 5
【样例输出1】
3
【样例输入2】
4 4
1 2
1 3
2 4
3 4
【样例输出2】
3
【数据范围】
对于30%的数据,1≤n,m≤10;
对于另外30%的数据,1≤n,m≤1,000,000,保证图是拓扑图;
对于100%的数据,1≤n,m≤1,000,000。
Related
In following contests: