Artifact 1f3d1cfa1b9a8b8a251abf74979b2be32b887f89:
0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 0a 2f 2f 20 53 74 72 6f 6e 67 6c 79 20 43 6f 6e .// Strongly Con
0050: 6e 65 63 74 65 64 20 43 6f 6d 70 6f 6e 65 6e 74 nected Component
0060: 20 6f 66 20 61 20 44 69 72 65 63 74 65 64 20 47 of a Directed G
0070: 72 61 70 68 0a 2f 2f 20 20 20 4f 28 45 29 0a 2f raph.// O(E)./
0080: 2f 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 62 79 /.// Verified by
0090: 0a 2f 2f 20 20 20 2d 20 53 52 4d 20 34 39 39 20 .// - SRM 499
00a0: 44 69 76 31 20 4c 56 33 0a 2f 2f 0a 2f 2f 20 55 Div1 LV3.//.// U
00b0: 73 69 6e 67 20 22 53 70 61 67 65 74 74 68 69 20 sing "Spagetthi
00c0: 53 6f 75 72 63 65 22 27 73 20 6f 6e 65 20 70 61 Source"'s one pa
00d0: 74 68 20 61 6c 67 6f 72 69 74 68 6d 0a 2f 2f 2d th algorithm.//-
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0100: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0110: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 74 65 ------------..te
0120: 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 mplate<typename
0130: 54 3e 0a 63 6c 61 73 73 20 49 64 47 65 6e 0a 7b T>.class IdGen.{
0140: 0a 09 6d 61 70 3c 54 2c 20 69 6e 74 3e 20 76 32 ..map<T, int> v2
0150: 69 64 5f 3b 0a 09 76 65 63 74 6f 72 3c 54 3e 20 id_;..vector<T>
0160: 20 20 69 64 32 76 5f 3b 0a 70 75 62 6c 69 63 3a id2v_;.public:
0170: 0a 09 69 6e 74 20 76 32 69 64 28 63 6f 6e 73 74 ..int v2id(const
0180: 20 54 26 20 76 29 20 7b 0a 09 09 69 66 28 20 21 T& v) {...if( !
0190: 76 32 69 64 5f 2e 63 6f 75 6e 74 28 76 29 20 29 v2id_.count(v) )
01a0: 20 7b 20 76 32 69 64 5f 5b 76 5d 20 3d 20 73 69 { v2id_[v] = si
01b0: 7a 65 28 29 3b 20 69 64 32 76 5f 2e 70 75 73 68 ze(); id2v_.push
01c0: 5f 62 61 63 6b 28 76 29 3b 20 7d 0a 09 09 72 65 _back(v); }...re
01d0: 74 75 72 6e 20 76 32 69 64 5f 5b 76 5d 3b 0a 09 turn v2id_[v];..
01e0: 7d 0a 09 63 6f 6e 73 74 20 54 26 20 69 64 32 76 }..const T& id2v
01f0: 28 69 6e 74 20 69 29 20 63 6f 6e 73 74 20 7b 20 (int i) const {
0200: 72 65 74 75 72 6e 20 69 64 32 76 5f 5b 69 5d 3b return id2v_[i];
0210: 20 7d 0a 09 69 6e 74 20 73 69 7a 65 28 29 20 63 }..int size() c
0220: 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e 20 69 64 onst { return id
0230: 32 76 5f 2e 73 69 7a 65 28 29 3b 20 7d 0a 7d 3b 2v_.size(); }.};
0240: 0a 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e ..template<typen
0250: 61 6d 65 20 56 65 72 74 3e 0a 63 6c 61 73 73 20 ame Vert>.class
0260: 53 43 43 0a 7b 0a 09 49 64 47 65 6e 3c 56 65 72 SCC.{..IdGen<Ver
0270: 74 3e 20 69 64 67 65 6e 3b 0a 09 76 65 63 74 6f t> idgen;..vecto
0280: 72 3c 20 76 65 63 74 6f 72 3c 69 6e 74 3e 20 3e r< vector<int> >
0290: 20 47 3b 0a 0a 70 75 62 6c 69 63 3a 0a 09 76 6f G;..public:..vo
02a0: 69 64 20 61 64 64 56 65 72 74 28 20 56 65 72 74 id addVert( Vert
02b0: 20 73 5f 20 29 0a 09 7b 0a 09 09 69 6e 74 20 73 s_ )..{...int s
02c0: 20 3d 20 69 64 67 65 6e 2e 76 32 69 64 28 73 5f = idgen.v2id(s_
02d0: 29 3b 0a 09 09 69 66 28 20 73 20 3e 3d 20 47 2e );...if( s >= G.
02e0: 73 69 7a 65 28 29 20 29 20 47 2e 72 65 73 69 7a size() ) G.resiz
02f0: 65 28 73 2b 31 29 3b 0a 09 7d 0a 0a 09 76 6f 69 e(s+1);..}...voi
0300: 64 20 61 64 64 45 64 67 65 28 20 56 65 72 74 20 d addEdge( Vert
0310: 73 5f 2c 20 56 65 72 74 20 74 5f 20 29 0a 09 7b s_, Vert t_ )..{
0320: 0a 09 09 69 6e 74 20 73 20 3d 20 69 64 67 65 6e ...int s = idgen
0330: 2e 76 32 69 64 28 73 5f 29 2c 20 74 20 3d 20 69 .v2id(s_), t = i
0340: 64 67 65 6e 2e 76 32 69 64 28 74 5f 29 3b 0a 09 dgen.v2id(t_);..
0350: 09 69 66 28 20 6d 61 78 28 73 2c 74 29 20 3e 3d .if( max(s,t) >=
0360: 20 47 2e 73 69 7a 65 28 29 20 29 20 47 2e 72 65 G.size() ) G.re
0370: 73 69 7a 65 28 6d 61 78 28 73 2c 74 29 2b 31 29 size(max(s,t)+1)
0380: 3b 0a 09 09 47 5b 73 5d 2e 70 75 73 68 5f 62 61 ;...G[s].push_ba
0390: 63 6b 28 74 29 3b 0a 09 7d 0a 0a 09 76 6f 69 64 ck(t);..}...void
03a0: 20 73 63 63 28 29 0a 09 7b 0a 09 09 69 6e 74 20 scc()..{...int
03b0: 4e 20 3d 20 47 2e 73 69 7a 65 28 29 3b 0a 09 09 N = G.size();...
03c0: 64 66 73 5f 6e 6f 2e 61 73 73 69 67 6e 28 4e 2c dfs_no.assign(N,
03d0: 20 30 29 3b 0a 09 09 64 66 73 5f 6c 6f 2e 61 73 0);...dfs_lo.as
03e0: 73 69 67 6e 28 4e 2c 20 30 29 3b 0a 09 09 70 65 sign(N, 0);...pe
03f0: 6e 64 69 6e 67 20 3d 20 73 74 61 63 6b 3c 69 6e nding = stack<in
0400: 74 3e 28 29 3b 0a 09 09 73 63 63 5f 69 64 2e 61 t>();...scc_id.a
0410: 73 73 69 67 6e 28 4e 2c 20 2d 31 29 3b 0a 09 09 ssign(N, -1);...
0420: 73 63 63 5f 6c 69 73 74 2e 63 6c 65 61 72 28 29 scc_list.clear()
0430: 3b 0a 09 09 73 63 63 5f 63 68 69 6c 64 72 65 6e ;...scc_children
0440: 2e 63 6c 65 61 72 28 29 3b 0a 09 09 66 6f 72 28 .clear();...for(
0450: 69 6e 74 20 76 3d 30 3b 20 76 3c 4e 3b 20 2b 2b int v=0; v<N; ++
0460: 76 29 0a 09 09 09 64 66 73 28 76 29 3b 0a 09 7d v)....dfs(v);..}
0470: 0a 0a 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 73 ...vector<int> s
0480: 63 63 5f 69 64 3b 20 2f 2f 20 77 68 69 63 68 20 cc_id; // which
0490: 73 63 63 20 64 6f 65 73 20 74 68 65 20 76 65 72 scc does the ver
04a0: 74 20 62 65 6c 6f 6e 67 20 74 6f 3f 0a 09 76 65 t belong to?..ve
04b0: 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 69 6e 74 ctor< vector<int
04c0: 3e 20 3e 20 73 63 63 5f 6c 69 73 74 3b 20 20 20 > > scc_list;
04d0: 20 20 2f 2f 20 6c 69 73 74 20 6f 66 20 6e 6f 64 // list of nod
04e0: 65 73 20 69 6e 20 74 68 65 20 73 63 63 0a 09 76 es in the scc..v
04f0: 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 69 6e ector< vector<in
0500: 74 3e 20 3e 20 73 63 63 5f 63 68 69 6c 64 72 65 t> > scc_childre
0510: 6e 3b 20 2f 2f 20 66 6f 72 65 73 74 20 72 65 6c n; // forest rel
0520: 61 74 69 6f 6e 73 68 69 70 20 6f 66 20 73 63 63 ationship of scc
0530: 73 0a 0a 70 72 69 76 61 74 65 3a 0a 09 69 6e 74 s..private:..int
0540: 20 6e 6f 3b 0a 09 76 65 63 74 6f 72 3c 69 6e 74 no;..vector<int
0550: 3e 20 64 66 73 5f 6e 6f 3b 20 2f 2f 20 31 2d 6f > dfs_no; // 1-o
0560: 72 69 67 69 6e 20 64 66 73 2d 76 69 73 69 74 20 rigin dfs-visit
0570: 49 44 0a 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 ID..vector<int>
0580: 64 66 73 5f 6c 6f 3b 20 2f 2f 20 74 68 65 20 6c dfs_lo; // the l
0590: 65 61 73 74 20 49 44 20 69 6e 20 74 68 65 20 76 east ID in the v
05a0: 65 72 74 27 73 20 73 63 63 0a 09 73 74 61 63 6b ert's scc..stack
05b0: 3c 69 6e 74 3e 20 70 65 6e 64 69 6e 67 3b 20 2f <int> pending; /
05c0: 2f 20 63 75 72 72 65 6e 74 20 75 6e 63 6c 61 73 / current unclas
05d0: 73 69 67 69 65 64 20 76 65 72 74 73 0a 0a 09 76 sigied verts...v
05e0: 6f 69 64 20 64 66 73 28 69 6e 74 20 76 29 0a 09 oid dfs(int v)..
05f0: 7b 0a 09 09 2f 2f 20 76 69 73 69 74 20 76 20 69 {...// visit v i
0600: 66 20 6e 6f 74 20 79 65 74 0a 09 09 69 66 28 20 f not yet...if(
0610: 64 66 73 5f 6e 6f 5b 76 5d 20 29 0a 09 09 09 72 dfs_no[v] )....r
0620: 65 74 75 72 6e 3b 0a 09 09 64 66 73 5f 6e 6f 5b eturn;...dfs_no[
0630: 76 5d 20 3d 20 64 66 73 5f 6c 6f 5b 76 5d 20 3d v] = dfs_lo[v] =
0640: 20 2b 2b 6e 6f 3b 0a 09 09 70 65 6e 64 69 6e 67 ++no;...pending
0650: 2e 70 75 73 68 28 76 29 3b 0a 0a 09 09 2f 2f 20 .push(v);....//
0660: 76 69 73 69 74 20 63 68 69 6c 64 72 65 6e 0a 09 visit children..
0670: 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c .for(int i=0; i<
0680: 47 5b 76 5d 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 G[v].size(); ++i
0690: 29 20 7b 0a 09 09 09 69 6e 74 20 75 20 3d 20 47 ) {....int u = G
06a0: 5b 76 5d 5b 69 5d 3b 0a 09 09 09 64 66 73 28 20 [v][i];....dfs(
06b0: 75 20 29 3b 0a 09 09 09 69 66 28 20 73 63 63 5f u );....if( scc_
06c0: 69 64 5b 75 5d 20 3d 3d 20 2d 31 20 29 0a 09 09 id[u] == -1 )...
06d0: 09 09 64 66 73 5f 6c 6f 5b 76 5d 20 3d 20 6d 69 ..dfs_lo[v] = mi
06e0: 6e 28 20 64 66 73 5f 6c 6f 5b 76 5d 2c 20 64 66 n( dfs_lo[v], df
06f0: 73 5f 6c 6f 5b 75 5d 20 29 3b 0a 09 09 7d 0a 0a s_lo[u] );...}..
0700: 09 09 2f 2f 20 77 68 65 6e 20 76 20 69 73 20 74 ..// when v is t
0710: 68 65 20 72 65 70 72 65 73 65 6e 74 61 74 69 76 he representativ
0720: 65 20 6f 66 20 73 63 63 0a 09 09 69 66 28 20 64 e of scc...if( d
0730: 66 73 5f 6e 6f 5b 76 5d 20 3d 3d 20 64 66 73 5f fs_no[v] == dfs_
0740: 6c 6f 5b 76 5d 20 29 20 7b 0a 09 09 09 76 65 63 lo[v] ) {....vec
0750: 74 6f 72 3c 69 6e 74 3e 20 73 63 63 3b 0a 09 09 tor<int> scc;...
0760: 09 66 6f 72 28 3b 3b 29 20 7b 0a 09 09 09 09 69 .for(;;) {.....i
0770: 6e 74 20 77 20 3d 20 70 65 6e 64 69 6e 67 2e 74 nt w = pending.t
0780: 6f 70 28 29 3b 20 70 65 6e 64 69 6e 67 2e 70 6f op(); pending.po
0790: 70 28 29 3b 0a 09 09 09 09 73 63 63 2e 70 75 73 p();.....scc.pus
07a0: 68 5f 62 61 63 6b 28 77 29 3b 0a 09 09 09 09 73 h_back(w);.....s
07b0: 63 63 5f 69 64 5b 77 5d 20 3d 20 73 63 63 5f 6c cc_id[w] = scc_l
07c0: 69 73 74 2e 73 69 7a 65 28 29 3b 0a 09 09 09 09 ist.size();.....
07d0: 69 66 28 20 77 20 3d 3d 20 76 20 29 20 62 72 65 if( w == v ) bre
07e0: 61 6b 3b 0a 09 09 09 7d 0a 09 09 09 73 63 63 5f ak;....}....scc_
07f0: 6c 69 73 74 2e 70 75 73 68 5f 62 61 63 6b 28 73 list.push_back(s
0800: 63 63 29 3b 0a 0a 09 09 09 73 65 74 3c 69 6e 74 cc);.....set<int
0810: 3e 20 63 68 69 6c 64 72 65 6e 3b 0a 09 09 09 66 > children;....f
0820: 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c 73 63 or(int j=0; j<sc
0830: 63 2e 73 69 7a 65 28 29 3b 20 2b 2b 6a 29 0a 09 c.size(); ++j)..
0840: 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
0850: 69 3c 47 5b 73 63 63 5b 6a 5d 5d 2e 73 69 7a 65 i<G[scc[j]].size
0860: 28 29 3b 20 2b 2b 69 29 0a 09 09 09 09 09 63 68 (); ++i)......ch
0870: 69 6c 64 72 65 6e 2e 69 6e 73 65 72 74 28 20 73 ildren.insert( s
0880: 63 63 5f 69 64 5b 47 5b 73 63 63 5b 6a 5d 5d 5b cc_id[G[scc[j]][
0890: 69 5d 5d 20 29 3b 0a 09 09 09 63 68 69 6c 64 72 i]] );....childr
08a0: 65 6e 2e 65 72 61 73 65 28 73 63 63 5f 69 64 5b en.erase(scc_id[
08b0: 76 5d 29 3b 0a 09 09 09 73 63 63 5f 63 68 69 6c v]);....scc_chil
08c0: 64 72 65 6e 2e 70 75 73 68 5f 62 61 63 6b 28 20 dren.push_back(
08d0: 76 65 63 74 6f 72 3c 69 6e 74 3e 28 63 68 69 6c vector<int>(chil
08e0: 64 72 65 6e 2e 62 65 67 69 6e 28 29 2c 20 63 68 dren.begin(), ch
08f0: 69 6c 64 72 65 6e 2e 65 6e 64 28 29 29 20 29 3b ildren.end()) );
0900: 0a 09 09 7d 0a 09 7d 0a 7d 3b 0a ...}..}.};.