Artifact e473bfcfb4e00b1656b29acf3d1a2c169c48361e:
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: 73 73 20 61 6c 67 6f 72 69 74 68 6d 0a 2f 2f 2d ss 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: 6e 6f 20 3d 20 30 3b 20 2f 2f 20 77 68 61 74 65 no = 0; // whate
03d0: 76 65 72 20 73 6d 61 6c 6c 20 65 6e 6f 75 67 68 ver small enough
03e0: 0a 09 09 64 66 73 5f 6e 6f 2e 61 73 73 69 67 6e ...dfs_no.assign
03f0: 28 4e 2c 20 30 29 3b 0a 09 09 64 66 73 5f 6c 6f (N, 0);...dfs_lo
0400: 2e 61 73 73 69 67 6e 28 4e 2c 20 30 29 3b 0a 09 .assign(N, 0);..
0410: 09 70 65 6e 64 69 6e 67 20 3d 20 73 74 61 63 6b .pending = stack
0420: 3c 69 6e 74 3e 28 29 3b 0a 09 09 73 63 63 5f 69 <int>();...scc_i
0430: 64 2e 61 73 73 69 67 6e 28 4e 2c 20 2d 31 29 3b d.assign(N, -1);
0440: 0a 09 09 73 63 63 5f 6c 69 73 74 2e 63 6c 65 61 ...scc_list.clea
0450: 72 28 29 3b 0a 09 09 73 63 63 5f 63 68 69 6c 64 r();...scc_child
0460: 72 65 6e 2e 63 6c 65 61 72 28 29 3b 0a 09 09 66 ren.clear();...f
0470: 6f 72 28 69 6e 74 20 76 3d 30 3b 20 76 3c 4e 3b or(int v=0; v<N;
0480: 20 2b 2b 76 29 0a 09 09 09 64 66 73 28 76 29 3b ++v)....dfs(v);
0490: 0a 09 7d 0a 0a 09 76 65 63 74 6f 72 3c 69 6e 74 ..}...vector<int
04a0: 3e 20 73 63 63 5f 69 64 3b 20 2f 2f 20 77 68 69 > scc_id; // whi
04b0: 63 68 20 73 63 63 20 64 6f 65 73 20 74 68 65 20 ch scc does the
04c0: 76 65 72 74 20 62 65 6c 6f 6e 67 20 74 6f 3f 0a vert belong to?.
04d0: 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c .vector< vector<
04e0: 69 6e 74 3e 20 3e 20 73 63 63 5f 6c 69 73 74 3b int> > scc_list;
04f0: 20 20 20 20 20 2f 2f 20 6c 69 73 74 20 6f 66 20 // list of
0500: 6e 6f 64 65 73 20 69 6e 20 74 68 65 20 73 63 63 nodes in the scc
0510: 0a 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 ..vector< vector
0520: 3c 69 6e 74 3e 20 3e 20 73 63 63 5f 63 68 69 6c <int> > scc_chil
0530: 64 72 65 6e 3b 20 2f 2f 20 66 6f 72 65 73 74 20 dren; // forest
0540: 72 65 6c 61 74 69 6f 6e 73 68 69 70 20 6f 66 20 relationship of
0550: 73 63 63 73 0a 0a 70 72 69 76 61 74 65 3a 0a 09 sccs..private:..
0560: 69 6e 74 20 6e 6f 3b 0a 09 76 65 63 74 6f 72 3c int no;..vector<
0570: 69 6e 74 3e 20 64 66 73 5f 6e 6f 3b 20 2f 2f 20 int> dfs_no; //
0580: 31 2d 6f 72 69 67 69 6e 20 64 66 73 2d 76 69 73 1-origin dfs-vis
0590: 69 74 20 49 44 0a 09 76 65 63 74 6f 72 3c 69 6e it ID..vector<in
05a0: 74 3e 20 64 66 73 5f 6c 6f 3b 20 2f 2f 20 74 68 t> dfs_lo; // th
05b0: 65 20 6c 65 61 73 74 20 49 44 20 69 6e 20 74 68 e least ID in th
05c0: 65 20 76 65 72 74 27 73 20 73 63 63 0a 09 73 74 e vert's scc..st
05d0: 61 63 6b 3c 69 6e 74 3e 20 70 65 6e 64 69 6e 67 ack<int> pending
05e0: 3b 20 2f 2f 20 63 75 72 72 65 6e 74 20 75 6e 63 ; // current unc
05f0: 6c 61 73 73 69 67 69 65 64 20 76 65 72 74 73 0a lassigied verts.
0600: 0a 09 76 6f 69 64 20 64 66 73 28 69 6e 74 20 76 ..void dfs(int v
0610: 29 0a 09 7b 0a 09 09 2f 2f 20 76 69 73 69 74 20 )..{...// visit
0620: 76 20 69 66 20 6e 6f 74 20 79 65 74 0a 09 09 69 v if not yet...i
0630: 66 28 20 64 66 73 5f 6e 6f 5b 76 5d 20 29 0a 09 f( dfs_no[v] )..
0640: 09 09 72 65 74 75 72 6e 3b 0a 09 09 64 66 73 5f ..return;...dfs_
0650: 6e 6f 5b 76 5d 20 3d 20 64 66 73 5f 6c 6f 5b 76 no[v] = dfs_lo[v
0660: 5d 20 3d 20 2b 2b 6e 6f 3b 0a 09 09 70 65 6e 64 ] = ++no;...pend
0670: 69 6e 67 2e 70 75 73 68 28 76 29 3b 0a 0a 09 09 ing.push(v);....
0680: 2f 2f 20 76 69 73 69 74 20 63 68 69 6c 64 72 65 // visit childre
0690: 6e 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b n...for(int i=0;
06a0: 20 69 3c 47 5b 76 5d 2e 73 69 7a 65 28 29 3b 20 i<G[v].size();
06b0: 2b 2b 69 29 20 7b 0a 09 09 09 69 6e 74 20 75 20 ++i) {....int u
06c0: 3d 20 47 5b 76 5d 5b 69 5d 3b 0a 09 09 09 64 66 = G[v][i];....df
06d0: 73 28 20 75 20 29 3b 0a 09 09 09 69 66 28 20 73 s( u );....if( s
06e0: 63 63 5f 69 64 5b 75 5d 20 3d 3d 20 2d 31 20 29 cc_id[u] == -1 )
06f0: 0a 09 09 09 09 64 66 73 5f 6c 6f 5b 76 5d 20 3d .....dfs_lo[v] =
0700: 20 6d 69 6e 28 20 64 66 73 5f 6c 6f 5b 76 5d 2c min( dfs_lo[v],
0710: 20 64 66 73 5f 6c 6f 5b 75 5d 20 29 3b 0a 09 09 dfs_lo[u] );...
0720: 7d 0a 0a 09 09 2f 2f 20 77 68 65 6e 20 76 20 69 }....// when v i
0730: 73 20 74 68 65 20 72 65 70 72 65 73 65 6e 74 61 s the representa
0740: 74 69 76 65 20 6f 66 20 73 63 63 0a 09 09 69 66 tive of scc...if
0750: 28 20 64 66 73 5f 6e 6f 5b 76 5d 20 3d 3d 20 64 ( dfs_no[v] == d
0760: 66 73 5f 6c 6f 5b 76 5d 20 29 20 7b 0a 09 09 09 fs_lo[v] ) {....
0770: 76 65 63 74 6f 72 3c 69 6e 74 3e 20 73 63 63 3b vector<int> scc;
0780: 0a 09 09 09 66 6f 72 28 3b 3b 29 20 7b 0a 09 09 ....for(;;) {...
0790: 09 09 69 6e 74 20 77 20 3d 20 70 65 6e 64 69 6e ..int w = pendin
07a0: 67 2e 74 6f 70 28 29 3b 20 70 65 6e 64 69 6e 67 g.top(); pending
07b0: 2e 70 6f 70 28 29 3b 0a 09 09 09 09 73 63 63 2e .pop();.....scc.
07c0: 70 75 73 68 5f 62 61 63 6b 28 77 29 3b 0a 09 09 push_back(w);...
07d0: 09 09 73 63 63 5f 69 64 5b 77 5d 20 3d 20 73 63 ..scc_id[w] = sc
07e0: 63 5f 6c 69 73 74 2e 73 69 7a 65 28 29 3b 0a 09 c_list.size();..
07f0: 09 09 09 69 66 28 20 77 20 3d 3d 20 76 20 29 20 ...if( w == v )
0800: 62 72 65 61 6b 3b 0a 09 09 09 7d 0a 09 09 09 73 break;....}....s
0810: 63 63 5f 6c 69 73 74 2e 70 75 73 68 5f 62 61 63 cc_list.push_bac
0820: 6b 28 73 63 63 29 3b 0a 0a 09 09 09 73 65 74 3c k(scc);.....set<
0830: 69 6e 74 3e 20 63 68 69 6c 64 72 65 6e 3b 0a 09 int> children;..
0840: 09 09 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a ..for(int j=0; j
0850: 3c 73 63 63 2e 73 69 7a 65 28 29 3b 20 2b 2b 6a <scc.size(); ++j
0860: 29 0a 09 09 09 09 66 6f 72 28 69 6e 74 20 69 3d ).....for(int i=
0870: 30 3b 20 69 3c 47 5b 73 63 63 5b 6a 5d 5d 2e 73 0; i<G[scc[j]].s
0880: 69 7a 65 28 29 3b 20 2b 2b 69 29 0a 09 09 09 09 ize(); ++i).....
0890: 09 63 68 69 6c 64 72 65 6e 2e 69 6e 73 65 72 74 .children.insert
08a0: 28 20 73 63 63 5f 69 64 5b 47 5b 73 63 63 5b 6a ( scc_id[G[scc[j
08b0: 5d 5d 5b 69 5d 5d 20 29 3b 0a 09 09 09 63 68 69 ]][i]] );....chi
08c0: 6c 64 72 65 6e 2e 65 72 61 73 65 28 73 63 63 5f ldren.erase(scc_
08d0: 69 64 5b 76 5d 29 3b 0a 09 09 09 73 63 63 5f 63 id[v]);....scc_c
08e0: 68 69 6c 64 72 65 6e 2e 70 75 73 68 5f 62 61 63 hildren.push_bac
08f0: 6b 28 20 76 65 63 74 6f 72 3c 69 6e 74 3e 28 63 k( vector<int>(c
0900: 68 69 6c 64 72 65 6e 2e 62 65 67 69 6e 28 29 2c hildren.begin(),
0910: 20 63 68 69 6c 64 72 65 6e 2e 65 6e 64 28 29 29 children.end())
0920: 20 29 3b 0a 09 09 7d 0a 09 7d 0a 7d 3b 0a );...}..}.};.