算法 {有向无环图DAG}

有向无环图DAG

定义

如果有向图 G = ( V , E ) G=(V,E) G=(V,E)满足:

1: 所有点是弱连通的;

2: E E E中不存在环;

相关定义

#DAG的森林#

由多个相互独立的DAG组合起来的图;

@DELI;

#(一级)叶子节点#

出度为0的点的集合;

#二级叶子节点#

将所有一级叶子节点(及其相关边)删除掉后, 新DAG的一级叶子节点集合 为 G G G的二级叶子节点;

#三级叶子节点#

将所有{一级,二级}叶子节点(及其相关边)删除掉后, 新DAG的一级叶子节点集合 为 G G G的二级叶子节点;

@DELI;

#起点#

入度为0的点的集合;

错误

性质

任意二级叶子节点X, 他的后驱节点 一定都是一级叶子节点;

任意三级叶子节点X, 他的后驱节点 一定存在二级叶子节点;

.d<--a-->b-->c对于a 他是三级叶子节点 后驱节点 既有二级 也有一级;

任意DAG图的拓扑序, 一定形如 [ . . . 四级 , 三级 , 二级 , 一级叶子节点 ] [... 四级, 三级, 二级, 一级叶子节点] [...四级,三级,二级,一级叶子节点];

@DELI;

+let H H H be the set of start-points and T T T the set of end-points in aWeakly-Connected-DAG;

.Any point (including H / T H/T H/T) must be reachable by at least one point of H H H and must can reach to at least one point of T T T;

.Any point a ∈ H a \in H a∈H and any point b ∈ T b \in T b∈T, a a a may not reach to b b b; e.g., ( a → b ) ( a → c ) ( d → c ) (a\to b) (a\to c) (d\to c) (a→b)(a→c)(d→c) where the start-point d d d cannot reach to the end-point b b b;

+The 最大路径独立集 (it is a set of points such that any two points of it are not accessible to each other) of a DAG, maybe not the H / T H/T H/T where H H H is the set of start-points and T T T the set of end-points;

.e.g., ( a → b ) ( a → c ) ( b → d ) ( c → d ) (a\to b) (a \to c) (b\to d) (c\to d) (a→b)(a→c)(b→d)(c→d), the 最大路径独立集 is ( b , c ) (b,c) (b,c)

+The transitive-graph of a DAG is also a DAG; (i.e., let E [ a ] [ b ] E[a][b] E[a][b] denotes an edge in the DAG, then performing Floyd-Boolean to get a new graph G G G, finally G G G would also be a DAG)

+Any path is DAG is Simple-Path (i.e., all points on the path are distinct);

+TheSource-Pointsof a DAG is the set of all points x x x such that d i n [ x ] = 0 din[ x] = 0 din[x]=0, also theEnd-Pointsis all points d o u t [ x ] = 0 dout[x] = 0 dout[x]=0;

.Any non-empty DAG must contains at leastoneSource-Points and End-Points. (let n , m n,m n,m be the number of Sources and Ends, then either n > 0 , m > 0 n>0, m>0 n>0,m>0 or n = m = 0 n=m=0 n=m=0, it is impossible that n = 0 , m > 0 n=0, m>0 n=0,m>0)

.A point x x x is both Source and Endif and only ifx x x is a Isolated-Point.

+Any two points a , b a,b a,b in a DAG maybe not Weakly-Connected (e.g., ( 1 → 2 ) ( 3 ) (1\to 2) (3) (1→2)(3) is a DAG); more precise, a , b a,b a,b either be Weakly-Connected, orNon-Connected; another phrase: a , b a,b a,b must be Non-Strongly-Connected.

+(DAG can does Topological-Sorting) is equivalent with (Any graph that can does Topological-Sorting, must is a DAG)

.The Topological-Sequence of a DAG maybe not unique.

+For any graph G = ( V , E ) G =(V,E) G=(V,E), after the performanceShrinking-SCC, it would becomes aDAG.

.Shrinking-SCC: let I d [ v ] Id[v] Id[v] denotes the SCC-ID of every point v ∈ V v \in V v∈V; Let G 1 = ( V 1 , E 1 ) G1 = (V1, E1) G1=(V1,E1) be a empty graph, and then iterating all edges ( a → b ) ∈ E (a \to b) \in E (a→b)∈E, add the edge I d [ a ] → I d [ b ] Id[a] \to Id[b] Id[a]→Id[b] into G 1 G1 G1whenI d [ a ] ≠ I d [ b ] Id[a] \neq Id[b] Id[a]=Id[b]. Finally, G 1 G1 G1 is a DAG.

.Moreover, G 1 G1 G1 has no Loop, but may contains Multiple-Edge (you can use Hashing to avoid it when adding edges into G 1 G1 G1);

For a Weakly-Connected DAG, let its Source be s 1 , s 2 , . . . , s n s1,s2,...,sn s1,s2,...,sn and its End be e 1 , e 2 , . . . , e m e1,e2,...,em e1,e2,...,em;

We build a Bipartite-Graph where L = ( s 1 , s 2 , . . . , s n ) , R = ( e 1 , e 2... , e m ) L = (s1,s2,..., sn), R = (e1,e2...,em) L=(s1,s2,...,sn),R=(e1,e2...,em); if s i si si can reach to e j ej ej, then we connected a edge between s i , e j si, ej si,ej in the Bipartite;

As a result, the Maximal-Match of this Bipartite is m i n ( n , m ) min( n, m) min(n,m) (i.e., Full-Matched)

.Cuz any two points s i , e j si, ej si,ej exists a path (i.e., if n < m n < m n<m, s i si si always has a Augmented-Path)

But if the DAG is not Weakly-Connected, it is not correct; e.g., if the DAG contains two Weakly-Connected-Sub-Graphs that are ( 2 , 3 ) ( 3 , 2 ) (2,3) (3,2) (2,3)(3,2) where ( 2 , 3 ) (2,3) (2,3) represents 2 2 2 Sources and 3 3 3 Ends;

The Maximal-Match is m i n ( 2 , 3 ) + m i n ( 3 , 2 ) = 4 min(2, 3) + min(3,2) = 4 min(2,3)+min(3,2)=4, not m i n ( 2 + 3 , 3 + 2 ) = 5 min(2+3, 3+2) = 5 min(2+3,3+2)=5

应用

最小路径点覆盖

If the graph is a DAG, 最小路径点覆盖 can be solved by Bipartite;

Let D D D be the DAG where all points are a 1 , a 2 , . . . , a n a1,a2,...,an a1,a2,...,an, now we construct a Bipartite B B B using below method

for( (ai -> aj) : all edges in D){B.add( ai, aj +|V|);}

In B B B, the L-Set are a 1 , . . . , a n a1,...,an a1,...,an and R-Set are a 1 ‾ , . . . , a n ‾ \overline{a1},...,\overline{an} a1,...,an where a i ‾ = a 1 + ∣ V ∣ \overline{ai} = a1 + |V| ai=a1+∣V∣ (no specific meaning, just making all a i ‾ \overline{ai} ai differs to a i ai ai in the Bipartite); (if D is not DAG, B is also a Bipartite)

(最小路径点覆盖) equals ∣ V ∣ − m |V| - m ∣V∣−m where m m m is the Maximal-Match of B B B;

@Delimiter

证明

+Cuz we only care about ∣ S ∣ |S| ∣S∣ where S S S is the 最小路径点覆盖, e.g., S = ( a , b , c ) ( d , e ) . . . S = (a,b,c) (d,e) ... S=(a,b,c)(d,e)... where every ( . . . ) (...) (...) denotes a path;

.We stipulate that a path ( a , b , c ) ∈ S (a,b,c) \in S (a,b,c)∈S actually denotes all paths with the form a → b → c a \to b \to c a→b→c (due to multiple edges between two points, so ( a , b , c ) (a,b,c) (a,b,c) may denotes many paths), it would not affect the calculation; cuz we focus on the number of ( ) ( ) ( ) () () () ()()(), not care about ( ? ) (?) (?).

+(路径点覆盖) → \to → (Matches in Bipartite)

.( a 1 , a 2 , . . . a i ) ( a x , . . . ) ( . . ) . . . (a1,a2, ... ai) (ax,...) (..) ... (a1,a2,...ai)(ax,...)(..)... is a 路径点覆盖, where the points in all paths are distinct, any directed edge a i → a j ai \to aj ai→aj in any path had been transformed into undirected edge ( a i − a j ‾ ) (ai - \overline{aj}) (ai−aj​) in B B B; we found that all such edges in B B B are disjoints, that is all these edges in B B B form a Match;

.e.g., a 路径点覆盖 ( a , b , c ) ( d , e ) ( f ) (a, b, c) (d, e) (f) (a,b,c)(d,e)(f) in DAG corresponds to a Match ( a − b ‾ ) ( b − c ‾ ) ( d − e ‾ ) (a-\overline{b}) (b-\overline{c}) (d- \overline{e}) (a−b)(b−c)(d−e) in D D D;

.This map is Injective; (if D is not DAG, this is also satisfies)

+(Matches in Bipartite) → \to → (路径点覆盖)

.For a match ( a i − a j ‾ ) ( ) ( ) . . . (ai-\overline{aj}) () () ... (ai−aj​)()()..., cuz every edge ( a − b ‾ ) (a-\overline{b}) (a−b) actually is a directed edge a → b a \to b a→b in DAG, from this view-point, firstly we write the match in the form ( a i , a j ‾ ) ( x x , x x ) . . . (ai,\overline{aj}) (xx,xx) ... (ai,aj​)(xx,xx)... where we call a ( x x ) (xx) (xx) be a path (corresponds to a Simple-Path in DAG); if there exists ( a , b ‾ ) ( c , d ‾ ) (a,\overline{b}) (c, \overline{d}) (a,b)(c,d) where b = c b=c b=c, then merge them to be ( a , b , d ‾ ) (a, b, \overline{d}) (a,b,d) (cuz two such edges a → b , b → c a\to b, b \to c a→b,b→c corresponds to a path a → b → c a\to b \to c a→b→c); proceeding this process, finally, every path is in the form ( a 1 , a 2 , . . . , a k ‾ ) (a1, a2, ..., \overline{ak}) (a1,a2,...,ak) ( a 1 ≠ a k a1 \neq ak a1=ak, cuz DAG has no circuit);

.All paths are distinct, that is there is no point belongs to multiple paths; Proof: ( a 1 , a 2 , a 3 ‾ ) ( a 4 , a 5 , a 6 ‾ ) (a1,a2,\overline{a3}) (a4,a5,\overline{a6}) (a1,a2,a3)(a4,a5,a6) all a 1 , a 2 , a 4 , a 5 a1, a2, a4, a5 a1,a2,a4,a5 (all points except the last-points) are distinct (due to they come from the left-set of original matches); all a 2 , a 3 ‾ , a 5 , a 6 ‾ a2, \overline{a3}, a5, \overline{a6} a2,a3,a5,a6 (all points except the first-points) are distinct (due to they also come from the right-set of the original matches); a i , a j ‾ ai, \overline{aj} ai,aj​ ( a i ai ai is the first-point in a path, a j ‾ \overline{aj} aj​ is the last-point in a path) are distinct (i.e., a i ≠ a j ai \neq aj ai=aj) (cuz the merge-process has finished, they must be in the same path, then it indicates that the path is a Circuit which is impossible is DAG)

.Finally, add all Isolated-Points; e.g., the match corresponds to paths ( a 1 , a 2 , a 3 ‾ ) ( a 4 , a 5 ‾ ) (a1,a2,\overline{a3}) (a4, \overline{a5}) (a1,a2,a3)(a4,a5) (there are 7 7 7 points in total), then add the isolated points a 6 , a 7 a6, a7 a6,a7; the new paths are ( a 1 , a 2 , a 3 ) ( a 4 , a 5 ) ( a 6 ) ( a 7 ) (a1,a2,a3) (a4,a5) (a6) (a7) (a1,a2,a3)(a4,a5)(a6)(a7) which is a 路径点覆盖

.Different matches correspond to different 路径点覆盖; so the map is Injective;

As a result, (路径点覆盖) and (matches) forms a Bijection;

Now, let’s consider the paths-count of a Match; all paths in a Match has two kinds (as mentioned above):1a self-path, i.e., a isolated-point ( a ) (a) (a), in this case, a a a must be a Unmatched-Point in L-Set under the match;2a path ( a 1 , . . . , a i ‾ ) (a1,...,\overline{ai}) (a1,...,ai), then a i ai ai (note that, not a i ‾ \overline{ai} ai must be a Unmatched-Point in L-Set under the match (if not (that is, it is a matched-point of L-Set), then it would be a non-last-point in a path, which would contradicts with the context a i ‾ \overline{ai} ai is a last-point);

.So, every path corresponds to a Unmatched-Point in L-Set; cuz these paths contains all points, so there would not exist a Unmatched-Point in L-Set with which no path corresponds;

.In a match, the paths-count equals the Unmatched-Points in L-Set, that is n − M n - M n−M where M M M is the match-count;

Therefore, 最小路径点覆盖 equals n − m n - m n−m where m m m is the maximal-match;

最小路径重复点覆盖

If the graph D D D is a DAG, (最小路径重复点覆盖) equals (最小路径点覆盖) in D D DD DD; where D D DD DD is the Transitivity-Graph of D D D (i.e., two edges a , b a,b a,b and b , c b,c b,c in D D D produce a new edge a , c a,c a,c)

@Delimiter

证明

A same stipulation as above, we use ( a , b , c ) (a,b,c) (a,b,c) denotes any path in the form a → b → c a\to b \to c a→b→c due to the multiple edges between two points; it would not affect, cuz we only focus on the paths-count, not the edges of a path;

If the graph D D D is a DAG, for a (路径重复点覆盖), we transform it to a Simplified-Form: if a point a a a occurs in two paths . . . a . . . ...a... ...a... and . . . a . . . ...a... ...a..., let’s focus on the first path1if a a a is the first-point or last-point ( a , . . . a, ... a,... or . . . , a ... , a ...,a) then remove this point from the path, all points are still coved;2if a a a is . . . x , a , y . . . ... x , a , y ... ...x,a,y..., then we use x , y x , y x,y to replace x , a , y x , a , y x,a,y (note that x , y x , y x,y no longer means a edge in D D D (cuz D D D may have no edge between them), it is just a transformation), now all points are still covered;

Finally, these paths cover all all points only once (that is, becomes a 路径点覆盖); but as discussed above, it is not a 路径点覆盖 of D D D (a path . . . , x , y , . . . ..., x,y, ... ...,x,y,... in 路径点覆盖 where x , y x,y x,y must denotes a edge in a DAG, while there maybe no edge x , y x,y x,y in D D D);

So, we need to add such edges x , y x,y x,y into D D D (i.e., run Floyd-Boolean, two edges a , b a,b a,b and b , c b,c b,c produces a new edge a , c a,c a,c); the new graph would still be a DAG; let the new DAG be D D DD DD;

It can be proved that, 路径重复点覆盖 in D D D is equivalent to 路径重复点覆盖 in D D DD DD (cuz if a path uses an edge x , y x,y x,y in D D DD DD, then it can be decomposed into x , . . . , y x,...,y x,...,y where all edges are raw-edges)

As a result, any 路径重复点覆盖 in D D DD DD, using the above Simplified-Form operation, it can be transformed to a 路径点覆盖 in D D DD DD; and all 路径点覆盖 are also 路径重复点覆盖;

so we just calculate the 最小路径点覆盖 in D D DD DD which equals to the 最小路径重复点覆盖 in D D DD DD (also in D D D);

@Delimiter

例题

AcWing-379. 捉迷藏

路径独立集

If D D D is a DAG, (最大独立集) equals (最小路径重复点覆盖) in D D D;

@Delimiter

证明

@Unfinished

至少新添加几条边,使得DAG成为SCC

AcWing-367. 学校网络

For a DAG ( V , E ) (V, E) (V,E), let x x x denoted the answer;

1x = 0 x = 0 x=0 if ∣ V ∣ = 1 |V| = 1 ∣V∣=1

2otherwise x = m a x ( s , e ) x = max(s, e) x=max(s,e) where s s s is the number of Source-Points and e e e is the End-Points;

For a DAG G G G, let its Source be s 1 , s 2 , . . . , s n s1,s2,...,sn s1,s2,...,sn and its End be e 1 , e 2 , . . . , e m e1,e2,...,em e1,e2,...,em; you can imagine that a graph B B B which consists of these points, and if s i si si can reach to e j ej ej then B B B has a edge s i → e j si \to ej si→ej; B B B is also a DAG, and once you make B B B a SCC then G G G is also a SCC.

Proof: for any points a , b a,b a,b in G G G and suppose that s 1 → a → e 1 s1 \to a \to e1 s1→a→e1 and s 2 → b → e 2 s2 \to b \to e2 s2→b→e2 where → \to → meanscan reach; cuz s 1 , s 2 , e 1 , e 2 s1,s2,e1,e2 s1,s2,e1,e2 are Strongly-Connected, there exists two paths a → e 1 → s 2 → b a \to e1 \to s2 \to b a→e1→s2→b and b → e 2 → s 1 → a b \to e2 \to s1 \to a b→e2→s1→a, therefore a , b a,b a,b are Strongly-Connected;

A easy device is adding these edges s i → s i − 1 si \to s_{i-1} si→si−1​ and e i → e i + 1 ei \to e_{i+1} ei→ei+1​ and e m → s 1 em \to s1 em→s1, the answer is ( n − 1 ) + ( m − 1 ) + 1 (n-1) + (m-1) + 1 (n−1)+(m−1)+1, but it is not the optimal choice;

The correct approach involves the notion of Bipartite-Graph as mentions above.

A DAG G G G, corresponds to a Bipartite-Graph B B B where L = ( s 1 , s 2 , . . . , s n ) , R = ( e 1 , . . . , e m ) L = (s1,s2,...,sn), R = (e1,...,em) L=(s1,s2,...,sn),R=(e1,...,em) where L L L is the set of points whose d i n = 0 din = 0 din=0 and R R R for d o u t = 0 dout = 0 dout=0, if s i si si can reach to e j ej ej then there is a edge s i → e j si \to ej si→ej in B B B; It is obvious that B B B is also aDAG;There is a very crucial property on of this Partite: any point must has a edge(there exists a edge s i → ? si \to ? si→? or ? → e i ? \to ei ?→ei, ∀ s i , e j \forall si, ej ∀si,ej)

Our goal is to make B B B becomes a SCC;

The whole process is:

Originally, G G G is DAG with B B B as its Bipartite, so we have ∣ L ∣ > 0 , ∣ R ∣ > 0 |L| >0, |R| > 0 ∣L∣>0,∣R∣>0;

1If m i n ( ∣ L ∣ , ∣ R ∣ ) ≥ 2 min( |L|, |R| ) \geq 2 min(∣L∣,∣R∣)≥2, then there must exists at leasttwomatches on B B B;

.Disproof: let l 1 , l 2 , r 1 , r 2 l1,l2, r1,r2 l1,l2,r1,r2, if the maximal-match is 1 1 1, e.g., the only match is l 1 − r 1 l1-r1 l1−r1, then all l i → r 1 li \to r1 li→r1 (if not, l i − r i li - ri li−ri is another match); let’s consider the r 2 r2 r2, if l 1 − r 2 l1-r2 l1−r2 then l 1 − r 2 , l 2 − r 1 l1-r2, l2-r1 l1−r2,l2−r1 is valid; otherwise l i − r 2 li-r2 li−r2 then l 1 − r 1 , l i − r 2 l1-r1, li-r2 l1−r1,li−r2 is also valid. Therefore, there must has at least 2 2 2 matches.

.we choose 2 2 2 matches, e.g., l 1 − r 1 , l 2 − r 2 l1-r1, l2-r2 l1−r1,l2−r2,Add a new edger 1 → l 2 r1 \to l2 r1→l2; now r 1 , l 2 r1, l2 r1,l2 is no longer Source or End, so we need remove them from B B B; Operation:1remover1, l2from B B B2Add new edges to B B B (add edge l i → r j li \to rj li→rj if l i → r 1 ∧ l 2 → r j li \to r1 \land l2 \to rj li→r1∧l2→rj) In fact, the new B B B is the Bipartite of the graph (maybe not DAG) ( V , E + ( r 1 → l 2 ) (V, E + (r1 \to l2) (V,E+(r1→l2); the new B B B also has the property: any points has at least one edge; so continue this process until m i n ( ∣ L ∣ , ∣ R ∣ ) < 2 min( |L|, |R|) < 2 min(∣L∣,∣R∣)<2;

2Now, m i n ( ∣ L ∣ , ∣ R ∣ ) = 1 min( |L|, |R|) = 1 min(∣L∣,∣R∣)=1 (it is impossible that it equals 0 0 0, cuz each process above will cause m i n ( ∣ L ∣ , ∣ R ∣ ) − 1 min( |L|, |R|) - 1 min(∣L∣,∣R∣)−1; if ∣ L ∣ = 1 |L| = 1 ∣L∣=1, for the property of B B B we have that there have edges l 1 → r i ∀ r i l1 \to ri \quad \forall ri l1→ri∀ri, so we add edge r i → r i + 1 ri \to r_{i+1} ri→ri+1​ and r n → l 1 rn \to l1 rn→l1 (the similar device for the case ∣ R ∣ = 1 |R| = 1 ∣R∣=1), then B B B would become a SCC; that is, add m a x ( L , R ) max( L, R) max(L,R) edges;

Therefore, the total count is: let k k k be the count of process1(add k k k edges, and causes ∣ L ∣ , ∣ R ∣ |L|, |R| ∣L∣,∣R∣ minus k k k), at2we will add m a x ( L − k , R − k ) max( L - k, R - k) max(L−k,R−k) edges, so m a x ( L − k , R − k ) + k = m a x ( L , R ) max( L - k, R - k) + k = max( L, R) max(L−k,R−k)+k=max(L,R)

Pseudocode:

Add_answer( int a, int b); //< add a new edge (a -> b) on G, it would be called `max(n, m)` times.G; //< DAG with Source (s1,...,sn), End (e1,...,em)B; //< The Bipartite-Graph of `G`L = {s1, ..., sn}; //< The left-set of `B`R = {e1, ..., em}; //< The right-set of `B`for( si){for( ej){if( si can reach to ej){B.add_edge( si, ej);}}}int l = n, r = m;while( min( l, r) >= 2){find two matches (denoted `l1-r1, l2-r2`);Add_answer( r1, l2);for( li : L){for( rj : R){if( there is a edge `li -> r1` && `l2 -> rj){B.add_edge( li, rj);}}remove `l1,r2` from `B`;remove `l1` from `L`, remove `r2` from `R`;-- l, -- r;}// now, min(l, r) = 1if( l <= r){for( int i = 0; i + 1 < r; ++i){Add_answer( R[i], R[i+1]);}Add_answer( R[r-1], L[0]);}else{for( int i = 0; i + 1 < l; ++i){Add_answer( L[i+1], L[i]);}Add_answer( R[0], L[0]);}

@Delimiter

A Wrong Understanding

A wrong-understanding of the above idea is, let the maximal-match of B B B is k k k, l 1 − r 1 , . . . , l k − r k l1-r1, ..., lk-rk l1−r1,...,lk−rk, so there left ( n − k ) + ( m − k ) (n-k) + (m-k) (n−k)+(m−k) unmatched. Therefore, we connect k − 1 k-1 k−1 edges r i → l i + 1 ri \to l_{i+1} ri→li+1​, and ( n − k ) + ( m − k ) + 1 (n-k) +(m-k) +1 (n−k)+(m−k)+1 edges r k → . . . → l 1 rk \to ... \to l1 rk→...→l1;

This is wrong, e.g., G = ( l 1 − r 1 ) ( l 2 − r 1 ) ( l 3 − r 2 ) ( l 3 − r 3 ) G = (l1-r1) (l2-r1) (l3-r2) (l3-r3) G=(l1−r1)(l2−r1)(l3−r2)(l3−r3) (its Bipartite-Graph B B B is the same as G G G), the maximal-match is 2 2 2, let it be ( l 1 − r 1 ) ( l 3 − r 2 ) (l1-r1) (l3-r2) (l1−r1)(l3−r2), and l 2 , r 3 l2, r3 l2,r3 are unmatched, then we add edge r 1 → l 3 r1 \to l3 r1→l3 and r 2 → l 2 → r 3 → l 1 r2 \to l2 \to r3 \to l1 r2→l2→r3→l1 ( 4 4 4 edges in total), surely it also becomes a SCC, but this is not the optimal choice (e.g., r 2 → l 1 , r 3 → l 2 , r 1 → l 3 r2\to l1, r3\to l2, r1 \to l3 r2→l1,r3→l2,r1→l3 is also a SCC with 3 3 3 edges)

The correct construction-process based on the idea discussed above is,

1Firstly, we choose two matches ( l 1 − r 1 ) ( l 3 − r 2 ) (l1-r1) (l3-r2) (l1−r1)(l3−r2) of B B B, add a edge r 1 → l 3 r1 \to l3 r1→l3, subsequently r 1 , l 3 r1, l3 r1,l3 are no longer the Source/End-Points in the new G 1 = G + ( r 1 → l 3 ) G1 = G + (r1 \to l3) G1=G+(r1→l3), the new Bipartite-Graph B 1 B1 B1 of the new graph G 1 G1 G1 becomes ( l 1 − r 2 ) ( l 1 − r 3 ) ( l 2 − r 2 ) ( l 2 − r 3 ) (l1-r2) (l1-r3) (l2-r2) (l2-r3) (l1−r2)(l1−r3)(l2−r2)(l2−r3)

2Secondly, choose two matches ( l 1 − r 2 ) ( l 2 − r 3 ) (l1-r2) (l2-r3) (l1−r2)(l2−r3) of B B B, add a edge r 2 → l 2 r2 \to l2 r2→l2, the new B 2 B2 B2 of the new graph G 2 = G 1 + ( r 2 → l 2 ) G2 = G1 + (r2 \to l2) G2=G1+(r2→l2) becomes l 1 − r 3 l1-r3 l1−r3

3Finally, the understanding here is vital. the current B B B is l 1 − r 3 l1-r3 l1−r3, what does it means? There are only one Source in current G G G, one End; let’s see the current-graph G : ( l 1 ) → ( S C C ) → ( r 3 ) G: (l1) \to (SCC) \to (r3) G:(l1)→(SCC)→(r3) where S C C = ( l 2 , l 3 , r 1 , r 2 ) SCC = (l2,l3,r1,r2) SCC=(l2,l3,r1,r2), in other words, once we make B B B a SCC, then G G G is also a SCC; Therefore, we add r 3 → l 1 r3 \to l1 r3→l1 to make B B B a SCC;

One Tips:

At any step, every Closed-Sub-Graphs (Weakly-Connected) of G i Gi Gi, must has at least o n e one one Sources and Ends;

e.g., a Closed-Sub-Graph in G i Gi Gi would not be ( l 1 → r 1 ) ( r 1 → l 2 ) ( l 2 → r 1 ) (l1 \to r1) (r1 \to l2) (l2 \to r1) (l1→r1)(r1→l2)(l2→r1) which has 1 1 1 Source while 0 0 0 End. This case would never happened. Cuz each time we added a edge r i → l j ri \to lj ri→lj, it means there are l i → r i li \to ri li→ri and l j → r j lj \to rj lj→rj, so in the new Closed-Sub-Graph (after add the new edge) which contains this new edge, it would still contains l i li li as its Source and r j rj rj as its End.