forked from the-tourist/algo
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathhld_forest.cpp
309 lines (309 loc) · 7.63 KB
/
hld_forest.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
t e m p l a t e < t y p e n a m e T >
c l a s s h l d _ f o r e s t : p u b l i c l c a _ f o r e s t < T > {
p u b l i c :
u s i n g l c a _ f o r e s t < T > : : e d g e s ;
u s i n g l c a _ f o r e s t < T > : : g ;
u s i n g l c a _ f o r e s t < T > : : n ;
u s i n g l c a _ f o r e s t < T > : : i g n o r e ;
u s i n g l c a _ f o r e s t < T > : : p v ;
u s i n g l c a _ f o r e s t < T > : : s z ;
u s i n g l c a _ f o r e s t < T > : : p o s ;
u s i n g l c a _ f o r e s t < T > : : o r d e r ;
u s i n g l c a _ f o r e s t < T > : : d e p t h ;
u s i n g l c a _ f o r e s t < T > : : d f s ;
u s i n g l c a _ f o r e s t < T > : : d f s _ a l l ;
u s i n g l c a _ f o r e s t < T > : : l c a ;
u s i n g l c a _ f o r e s t < T > : : b u i l d _ l c a ;
v e c t o r < i n t > h e a d ;
v e c t o r < i n t > v i s i t e d ;
h l d _ f o r e s t ( i n t _ n ) : l c a _ f o r e s t < T > ( _ n ) {
v i s i t e d . r e s i z e ( n ) ;
}
v o i d b u i l d _ h l d ( c o n s t v e c t o r < i n t > & v s ) {
f o r ( i n t t r i e s = 0 ; t r i e s < 2 ; t r i e s + + ) {
i f ( v s . e m p t y ( ) ) {
d f s _ a l l ( ) ;
} e l s e {
o r d e r . c l e a r ( ) ;
f o r ( i n t v : v s ) {
a s s e r t ( d e p t h [ v ] = = - 1 ) ;
d f s ( v , f a l s e ) ;
}
a s s e r t ( ( i n t ) o r d e r . s i z e ( ) = = n ) ;
}
i f ( t r i e s = = 1 ) {
b r e a k ;
}
f o r ( i n t i = 0 ; i < n ; i + + ) {
i f ( g [ i ] . e m p t y ( ) ) {
c o n t i n u e ;
}
i n t b e s t = - 1 , b i d = 0 ;
f o r ( i n t j = 0 ; j < ( i n t ) g [ i ] . s i z e ( ) ; j + + ) {
i n t i d = g [ i ] [ j ] ;
i f ( i g n o r e ! = n u l l p t r & & i g n o r e ( i d ) ) {
c o n t i n u e ;
}
i n t v = e d g e s [ i d ] . f r o m ^ e d g e s [ i d ] . t o ^ i ;
i f ( p v [ v ] ! = i ) {
c o n t i n u e ;
}
i f ( s z [ v ] > b e s t ) {
b e s t = s z [ v ] ;
b i d = j ;
}
}
s w a p ( g [ i ] [ 0 ] , g [ i ] [ b i d ] ) ;
}
}
b u i l d _ l c a ( ) ;
h e a d . r e s i z e ( n ) ;
f o r ( i n t i = 0 ; i < n ; i + + ) {
h e a d [ i ] = i ;
}
f o r ( i n t i = 0 ; i < n - 1 ; i + + ) {
i n t x = o r d e r [ i ] ;
i n t y = o r d e r [ i + 1 ] ;
i f ( p v [ y ] = = x ) {
h e a d [ y ] = h e a d [ x ] ;
}
}
}
v o i d b u i l d _ h l d ( i n t v ) {
b u i l d _ h l d ( v e c t o r < i n t > ( 1 , v ) ) ;
}
v o i d b u i l d _ h l d _ a l l ( ) {
b u i l d _ h l d ( v e c t o r < i n t > ( ) ) ;
}
/ *
v e c t o r < p a i r < i n t , i n t > > g e t _ p a t h ( i n t x , i n t y ) {
v e c t o r < p a i r < i n t , i n t > > p a t h [ 2 ] ;
i n t z = l c a ( x , y ) ;
f o r ( i n t i d = 0 ; i d < 2 ; i d + + ) {
i n t v = ( i d = = 0 ? x : y ) ;
w h i l e ( v ! = z ) {
i f ( d e p t h [ h e a d [ v ] ] < = d e p t h [ z ] ) {
p a t h [ i d ] . e m p l a c e _ b a c k ( p o s [ z ] + 1 , p o s [ v ] ) ;
b r e a k ;
}
p a t h [ i d ] . e m p l a c e _ b a c k ( p o s [ h e a d [ v ] ] , p o s [ v ] ) ;
v = p v [ h e a d [ v ] ] ;
}
}
v e c t o r < p a i r < i n t , i n t > > r e t ;
f o r ( i n t i = 0 ; i < ( i n t ) p a t h [ 0 ] . s i z e ( ) ; i + + ) {
r e t . e m p l a c e _ b a c k ( p a t h [ 0 ] [ i ] . s e c o n d , p a t h [ 0 ] [ i ] . f i r s t ) ;
}
r e t . e m p l a c e _ b a c k ( - 1 , p o s [ z ] ) ;
f o r ( i n t i = ( i n t ) p a t h [ 1 ] . s i z e ( ) - 1 ; i > = 0 ; i - - ) {
r e t . p u s h _ b a c k ( p a t h [ 1 ] [ i ] ) ;
}
r e t u r n r e t ;
/ / r e t u r n s s e g m e n t s o f t h e p a t h :
/ / f i r s t f r o m x t o l c a , r e v e r s e d s e g m e n t s
/ / t h e n ( - 1 , p o s [ l c a ] )
/ / t h e n f r o m l c a t o y , d i r e c t s e g m e n t s
/ / b u t i n m o s t c a s e s , a p p l y _ o n _ p a t h s h o u l d b e e n o u g h
}
* /
b o o l a p p l y _ o n _ p a t h ( i n t x , i n t y , b o o l w i t h _ l c a , f u n c t i o n < v o i d ( i n t , i n t , b o o l ) > f ) {
/ / f ( x , y , u p ) : u p - - w h e t h e r t h i s p a r t o f t h e p a t h g o e s u p
a s s e r t ( ! h e a d . e m p t y ( ) ) ;
i n t z = l c a ( x , y ) ;
i f ( z = = - 1 ) {
r e t u r n f a l s e ;
}
{
i n t v = x ;
w h i l e ( v ! = z ) {
i f ( d e p t h [ h e a d [ v ] ] < = d e p t h [ z ] ) {
f ( p o s [ z ] + 1 , p o s [ v ] , t r u e ) ;
b r e a k ;
}
f ( p o s [ h e a d [ v ] ] , p o s [ v ] , t r u e ) ;
v = p v [ h e a d [ v ] ] ;
}
}
i f ( w i t h _ l c a ) {
f ( p o s [ z ] , p o s [ z ] , f a l s e ) ;
}
{
i n t v = y ;
i n t c n t _ v i s i t e d = 0 ;
w h i l e ( v ! = z ) {
i f ( d e p t h [ h e a d [ v ] ] < = d e p t h [ z ] ) {
f ( p o s [ z ] + 1 , p o s [ v ] , f a l s e ) ;
b r e a k ;
}
v i s i t e d [ c n t _ v i s i t e d + + ] = v ;
v = p v [ h e a d [ v ] ] ;
}
f o r ( i n t a t = c n t _ v i s i t e d - 1 ; a t > = 0 ; a t - - ) {
v = v i s i t e d [ a t ] ;
f ( p o s [ h e a d [ v ] ] , p o s [ v ] , f a l s e ) ;
}
}
r e t u r n t r u e ;
}
} ;