Differences From Artifact [1f3d1cfa1b9a8b8a]:
- File
lib/graph/scc.cpp
- 2011-10-08 15:42:58 - part of checkin [b57cc94f1b] on branch trunk - Library for SCC added and verified. (user: kinaba) [annotate]
To Artifact [b0ca04383cc7283f]:
- File
lib/graph/scc.cpp
- 2012-09-08 04:01:47 - part of checkin [109f2a9050] on branch trunk - 555 (user: kinaba) [annotate]
2 //------------------------------------------------------------- 2 //-------------------------------------------------------------
3 // Strongly Connected Component of a Directed Graph 3 // Strongly Connected Component of a Directed Graph
4 // O(E) 4 // O(E)
5 // 5 //
6 // Verified by 6 // Verified by
7 // - SRM 499 Div1 LV3 7 // - SRM 499 Div1 LV3
8 // 8 //
9 // Using "Spagetthi Source"'s one path algorithm | 9 // Using "Spagetthi Source"'s one pass algorithm
10 //------------------------------------------------------------- 10 //-------------------------------------------------------------
11 11
12 template<typename T> 12 template<typename T>
13 class IdGen 13 class IdGen
14 { 14 {
15 map<T, int> v2id_; 15 map<T, int> v2id_;
16 vector<T> id2v_; 16 vector<T> id2v_;