hdu 1269 Tarjanテンプレート強連通成分の個数を求める
迷宮の城
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 27125 Accepted Submission(s): 11544 Problem Descriptionは希ちゃんの方向感覚を訓練するため、Gardonは大きな城を建てました.中にはN部屋(N<=10000)とM通路(M<=10000)があり、各通路は一方向です.つまり、ある通路がA部屋とB部屋につながっているとすれば、この通路を通ってA部屋からB部屋に着くことができると説明していますが、B部屋からA部屋に着くことは説明していません.Gardonは、任意のiとjに対して、少なくとも1つの経路が部屋iから部屋jまで、1つの経路が部屋jから部屋iまでつながっているかどうかを確認するプログラムを書く必要があります. Input入力には複数のデータのセットが含まれており、入力された最初の行にはNとMの2つの数があり、次のM行には1行あたり2つの数aとbがあり、1つのチャネルがA部屋からB部屋に来ることができることを示している.ファイルは最後に2つの0で終了します. Outputは入力された各グループのデータに対して、いずれの部屋も互いに接続されている場合は「Yes」を出力し、そうでない場合は「No」を出力します. Sample Input 3 3 1 2 2 3 3 1 3 3 1 2 2 3 3 2 0 0 Sample Output Yes No
dfn【】各点の遍歴時のシーケンス番号//時間軸を表す
low【】この強連通成分を表すルートノードのシーケンス番号
最後にlow【】がdfn【】に等しい数はルートノードであり、強い連通成分を形成する
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 27125 Accepted Submission(s): 11544 Problem Descriptionは希ちゃんの方向感覚を訓練するため、Gardonは大きな城を建てました.中にはN部屋(N<=10000)とM通路(M<=10000)があり、各通路は一方向です.つまり、ある通路がA部屋とB部屋につながっているとすれば、この通路を通ってA部屋からB部屋に着くことができると説明していますが、B部屋からA部屋に着くことは説明していません.Gardonは、任意のiとjに対して、少なくとも1つの経路が部屋iから部屋jまで、1つの経路が部屋jから部屋iまでつながっているかどうかを確認するプログラムを書く必要があります. Input入力には複数のデータのセットが含まれており、入力された最初の行にはNとMの2つの数があり、次のM行には1行あたり2つの数aとbがあり、1つのチャネルがA部屋からB部屋に来ることができることを示している.ファイルは最後に2つの0で終了します. Outputは入力された各グループのデータに対して、いずれの部屋も互いに接続されている場合は「Yes」を出力し、そうでない場合は「No」を出力します. Sample Input 3 3 1 2 2 3 3 1 3 3 1 2 2 3 3 2 0 0 Sample Output Yes No
dfn【】各点の遍歴時のシーケンス番号//時間軸を表す
low【】この強連通成分を表すルートノードのシーケンス番号
最後にlow【】がdfn【】に等しい数はルートノードであり、強い連通成分を形成する
#include
using namespace std;
const int maxn=1e5+5;
int n,m,a,b,cnt,ans,dfn[maxn],low[maxn];
vector G[maxn];
void Tarjan(int u)
{
dfn[u]=low[u]=++cnt;//
for(int i=0; i