Artifact 4b76a9848cd0e992e6f251efe8a09bbb01321c02:
0000: 2f 2f 2d 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 0a ---------------.
0040: 2f 2f 20 54 72 65 65 20 44 46 53 20 6e 75 6d 62 // Tree DFS numb
0050: 65 72 69 6e 67 0a 2f 2f 20 20 20 4f 28 4e 29 0a ering.// O(N).
0060: 2f 2f 0a 2f 2f 20 47 20 3a 20 61 64 6a 61 63 65 //.// G : adjace
0070: 6e 74 20 6c 69 73 74 20 6f 66 20 61 20 67 72 61 nt list of a gra
0080: 70 68 20 28 66 6f 72 6d 69 6e 67 20 61 20 74 72 ph (forming a tr
0090: 65 65 29 0a 2f 2f 20 4c 61 62 65 6c 73 20 65 61 ee).// Labels ea
00a0: 63 68 20 6e 6f 64 65 20 76 20 61 73 20 64 66 73 ch node v as dfs
00b0: 5b 76 5d 2e 0a 2f 2f 20 49 6e 63 6c 75 73 69 76 [v]..// Inclusiv
00c0: 65 20 5b 64 66 73 5b 76 5d 2c 20 64 66 73 5f 65 e [dfs[v], dfs_e
00d0: 6e 64 5b 76 5d 5d 20 64 65 6e 6f 74 65 73 20 74 nd[v]] denotes t
00e0: 68 65 20 64 65 73 63 65 6e 64 61 6e 74 20 72 61 he descendant ra
00f0: 6e 67 65 2e 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 nge..//.// Verif
0100: 69 65 64 20 62 79 0a 2f 2f 20 20 20 2d 20 43 6f ied by.// - Co
0110: 64 65 66 6f 72 63 65 73 20 32 30 30 20 44 69 76 deforces 200 Div
0120: 31 20 44 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 1 D.//----------
0130: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0140: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0150: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0160: 2d 2d 2d 0a 0a 76 6f 69 64 20 64 66 73 5f 6e 75 ---..void dfs_nu
0170: 6d 62 65 72 69 6e 67 28 0a 09 69 6e 74 20 72 6f mbering(..int ro
0180: 6f 74 2c 0a 09 63 6f 6e 73 74 20 76 65 63 74 6f ot,..const vecto
0190: 72 3c 76 65 63 74 6f 72 3c 69 6e 74 3e 3e 26 20 r<vector<int>>&
01a0: 47 2c 20 76 65 63 74 6f 72 3c 69 6e 74 3e 26 20 G, vector<int>&
01b0: 64 66 73 2c 20 76 65 63 74 6f 72 3c 69 6e 74 3e dfs, vector<int>
01c0: 26 20 64 66 73 5f 65 6e 64 2c 0a 09 76 65 63 74 & dfs_end,..vect
01d0: 6f 72 3c 69 6e 74 3e 26 20 70 61 72 65 6e 74 5f or<int>& parent_
01e0: 6f 66 29 0a 7b 0a 09 69 6e 74 20 64 66 73 5f 6e of).{..int dfs_n
01f0: 75 6d 62 65 72 20 3d 20 72 6f 6f 74 3b 0a 09 64 umber = root;..d
0200: 66 73 5b 72 6f 6f 74 5d 20 3d 20 64 66 73 5f 6e fs[root] = dfs_n
0210: 75 6d 62 65 72 2b 2b 3b 0a 09 70 61 72 65 6e 74 umber++;..parent
0220: 5f 6f 66 5b 72 6f 6f 74 5d 20 3d 20 2d 31 3b 0a _of[root] = -1;.
0230: 0a 09 73 74 61 63 6b 3c 74 75 70 6c 65 3c 69 6e ..stack<tuple<in
0240: 74 2c 69 6e 74 2c 69 6e 74 3e 3e 20 73 74 6b 3b t,int,int>> stk;
0250: 0a 09 73 74 6b 2e 70 75 73 68 28 6d 61 6b 65 5f ..stk.push(make_
0260: 74 75 70 6c 65 28 2d 31 2c 20 72 6f 6f 74 2c 20 tuple(-1, root,
0270: 30 29 29 3b 0a 09 77 68 69 6c 65 28 21 73 74 6b 0));..while(!stk
0280: 2e 65 6d 70 74 79 28 29 29 20 7b 0a 09 09 69 6e .empty()) {...in
0290: 74 20 67 72 61 6e 64 70 61 72 65 6e 74 20 3d 20 t grandparent =
02a0: 67 65 74 3c 30 3e 28 73 74 6b 2e 74 6f 70 28 29 get<0>(stk.top()
02b0: 29 3b 0a 09 09 69 6e 74 20 70 61 72 65 6e 74 20 );...int parent
02c0: 20 20 20 20 20 3d 20 67 65 74 3c 31 3e 28 73 74 = get<1>(st
02d0: 6b 2e 74 6f 70 28 29 29 3b 0a 09 09 69 6e 74 20 k.top());...int
02e0: 63 68 69 6c 64 5f 69 64 20 20 20 20 3d 20 67 65 child_id = ge
02f0: 74 3c 32 3e 28 73 74 6b 2e 74 6f 70 28 29 29 3b t<2>(stk.top());
0300: 0a 09 09 73 74 6b 2e 70 6f 70 28 29 3b 0a 09 09 ...stk.pop();...
0310: 69 66 28 47 5b 70 61 72 65 6e 74 5d 2e 73 69 7a if(G[parent].siz
0320: 65 28 29 20 3c 3d 20 63 68 69 6c 64 5f 69 64 29 e() <= child_id)
0330: 20 7b 0a 09 09 09 64 66 73 5f 65 6e 64 5b 70 61 {....dfs_end[pa
0340: 72 65 6e 74 5d 20 3d 20 64 66 73 5f 6e 75 6d 62 rent] = dfs_numb
0350: 65 72 20 2d 20 31 3b 0a 09 09 09 63 6f 6e 74 69 er - 1;....conti
0360: 6e 75 65 3b 0a 09 09 7d 0a 09 09 73 74 6b 2e 70 nue;...}...stk.p
0370: 75 73 68 28 6d 61 6b 65 5f 74 75 70 6c 65 28 67 ush(make_tuple(g
0380: 72 61 6e 64 70 61 72 65 6e 74 2c 20 70 61 72 65 randparent, pare
0390: 6e 74 2c 20 63 68 69 6c 64 5f 69 64 2b 31 29 29 nt, child_id+1))
03a0: 3b 0a 0a 09 09 69 6e 74 20 6d 65 20 3d 20 47 5b ;....int me = G[
03b0: 70 61 72 65 6e 74 5d 5b 63 68 69 6c 64 5f 69 64 parent][child_id
03c0: 5d 3b 0a 09 09 69 66 28 6d 65 20 21 3d 20 67 72 ];...if(me != gr
03d0: 61 6e 64 70 61 72 65 6e 74 29 20 7b 0a 09 09 09 andparent) {....
03e0: 64 66 73 5b 6d 65 5d 20 3d 20 64 66 73 5f 6e 75 dfs[me] = dfs_nu
03f0: 6d 62 65 72 2b 2b 3b 0a 09 09 09 70 61 72 65 6e mber++;....paren
0400: 74 5f 6f 66 5b 6d 65 5d 20 3d 20 70 61 72 65 6e t_of[me] = paren
0410: 74 3b 0a 09 09 09 73 74 6b 2e 70 75 73 68 28 6d t;....stk.push(m
0420: 61 6b 65 5f 74 75 70 6c 65 28 70 61 72 65 6e 74 ake_tuple(parent
0430: 2c 20 6d 65 2c 20 30 29 29 3b 0a 09 09 7d 0a 09 , me, 0));...}..
0440: 7d 0a 7d 0a }.}.