POI - PA 2006 Crayfish (精神+翻譯)

沒co出來的有趣圖論                                                                                                    .


Round 4的題目好有趣但是好難orz




//*************************************

翻譯


給你一張有向圖，n<=10^4個頂點，m<=10^5條邊

有些邊是特殊的邊。

現在假設我拿i為起點，一開始只能逆的走(i.e.  a->b的邊只能從b走到a)

然後每經過一次特殊邊就得換方向(正走-> 逆走   反之亦然)

問你對於每個點的val值，val值定義為 從該點出發並要回到該點最多能經過多少其他的點



Input:

5 5
2 1 1
2 3 0
3 4 0
4 2 0
5 3 1

Output:

3
3
3
3
0

//***********************************


















雷:

把除了特殊的邊以外的正向圖及反向圖皆分別建出來，

每一條特殊的邊ex: a -> b


那麼就會從正向圖的a和反向圖的b做雙向邊


建完圖後SCC, 判重(同時走過一個點的正向跟反向)



















//************************************