Hex Artifact Content
Not logged in

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                 ...}..}.};.