1use std::collections::VecDeque;
2
3#[derive(Clone, Debug)]
4pub struct Graph {
5 pub n: usize,
6 pub graph: Vec<Vec<(usize, usize)>>,
7 pub rev: Vec<Vec<usize>>,
8 pub in_degrees: Vec<usize>,
9 pub out_degrees: Vec<usize>,
10 pub directed: bool,
11}
12
13impl Graph {
14 pub fn new(n: usize, directed: bool) -> Self {
15 let graph: Vec<Vec<(usize, usize)>> = vec![vec![]; n];
16 let in_degrees = vec![0; n];
17 let out_degrees = vec![0; n];
18 let rev = vec![vec![]; n];
19 Self {
20 n,
21 graph,
22 rev,
23 in_degrees,
24 out_degrees,
25 directed,
26 }
27 }
28
29 pub fn connect(&mut self, from: usize, to: usize, weight: usize) {
30 self.graph[from].push((to, weight));
31 self.out_degrees[from] += 1;
32 self.in_degrees[to] += 1;
33
34 if !self.directed {
35 self.graph[to].push((from, weight));
36 self.out_degrees[to] += 1;
37 self.in_degrees[from] += 1;
38 }
39 }
40
41 pub fn connect_unweighted(&mut self, from: usize, to: usize) {
42 self.graph[from].push((to, 1));
43 self.out_degrees[from] += 1;
44 self.in_degrees[to] += 1;
45
46 if !self.directed {
47 self.graph[to].push((from, 1));
48 self.out_degrees[to] += 1;
49 self.in_degrees[from] += 1;
50 }
51 }
52
53 pub fn connect_with_residual(&mut self, from: usize, to: usize, weight: usize) {
54 assert!(self.directed, "connect_with_residual only works in directed graph.");
55
56 self.graph[from].push((to, weight));
57 self.out_degrees[from] += 1;
58 self.in_degrees[to] += 1;
59
60 self.graph[to].push((from, 0));
61 self.out_degrees[to] += 1;
62 self.in_degrees[from] += 1;
63
64 self.rev[from].push(self.graph[to].len() - 1);
65 self.rev[to].push(self.graph[from].len() - 1);
66 }
67
68 pub fn in_degree(&self, u: usize) -> usize {
69 self.graph[u].len()
70 }
71
72 pub fn out_degree(&self, u: usize) -> usize {
73 self.graph[u].len()
74 }
75
76 pub fn connected(&self, u: usize, v: usize) -> bool {
77 self.graph[u].iter().filter(|&(k, _)| &v == k).count() > 0
78 }
79}
80
81#[cfg(test)]
82mod test_graph {
83 use crate::graph::Graph;
84
85 #[test]
86 fn it_works_directed() {
87 let mut graph = Graph::new(6, true);
88 graph.connect_unweighted(0, 1);
89 graph.connect_unweighted(2, 5);
90 graph.connect(1, 0, 10);
91 graph.connect(3, 4, 3);
92
93 let expected = vec![vec![(1, 1)], vec![(0, 10)], vec![(5, 1)], vec![(4, 3)], vec![], vec![]];
94 assert_eq!(graph.graph, expected);
95
96 assert!(graph.connected(0, 1));
97 assert!(graph.connected(1, 0));
98 assert!(graph.connected(2, 5));
99 assert!(!graph.connected(5, 2));
100 assert!(graph.connected(3, 4));
101 assert!(!graph.connected(4, 3));
102 assert!(!graph.connected(0, 2));
103 }
104
105 #[test]
106 fn it_works_undirected() {
107 let mut graph = Graph::new(6, false);
108 graph.connect_unweighted(0, 1);
109 graph.connect(2, 4, 10);
110 graph.connect(5, 3, 5);
111
112 let expected = vec![
113 vec![(1, 1)],
114 vec![(0, 1)],
115 vec![(4, 10)],
116 vec![(5, 5)],
117 vec![(2, 10)],
118 vec![(3, 5)],
119 ];
120 assert_eq!(graph.graph, expected);
121
122 assert!(graph.connected(0, 1));
123 assert!(graph.connected(1, 0));
124 assert!(graph.connected(2, 4));
125 assert!(graph.connected(4, 2));
126 assert!(graph.connected(3, 5));
127 assert!(graph.connected(5, 3));
128 assert!(!graph.connected(1, 3));
129 }
130
131 #[test]
132 fn it_works_circle() {
133 let mut graph = Graph::new(2, false);
134 graph.connect_unweighted(0, 1);
135
136 let expected = vec![vec![(1, 1)], vec![(0, 1)]];
137
138 assert_eq!(graph.graph, expected);
139 }
140
141 #[test]
142 fn it_works_multiple_edge() {
143 let mut graph = Graph::new(2, true);
144 graph.connect(0, 1, 10);
145 graph.connect_unweighted(0, 1);
146
147 let expected = vec![vec![(1, 10), (1, 1)], vec![]];
148 assert_eq!(graph.graph, expected);
149 }
150
151 #[test]
152 #[should_panic(expected = "connect_with_residual only works in directed graph.")]
153 fn it_does_not_work_residual() {
154 let mut graph = Graph::new(2, false);
155 graph.connect_with_residual(0, 1, 0)
156 }
157}
158
159#[derive(Debug, Clone)]
160pub struct BreadthFirstSearch {
161 graph: Graph,
162 dist: Vec<usize>,
163}
164
165impl BreadthFirstSearch {
166 const INF: usize = 100_000_000_000_000_000;
167
168 pub fn new(graph: Graph) -> Self {
169 let n = graph.n;
170 Self {
171 graph,
172 dist: vec![Self::INF; n],
173 }
174 }
175
176 pub fn search(&mut self, root: usize) {
177 let mut queue = std::collections::VecDeque::new();
178 queue.push_back(root);
179 self.dist[root] = 0;
180
181 while let Some(cur) = queue.pop_front() {
182 for &(next, _) in self.graph.graph[cur].iter() {
183 if self.dist[next] <= self.dist[cur] + 1 {
184 continue;
185 }
186
187 self.dist[next] = self.dist[next].min(self.dist[cur] + 1);
188 queue.push_back(next);
189 }
190 }
191 }
192}
193
194#[cfg(test)]
195mod test_bfs {
196 use crate::graph::BreadthFirstSearch;
197 use crate::graph::Graph;
198
199 #[test]
200 fn it_works() {
201 let mut graph = Graph::new(5, true);
202 graph.connect_unweighted(0, 1);
203 graph.connect_unweighted(1, 2);
204 graph.connect_unweighted(2, 4);
205
206 let mut bfs = BreadthFirstSearch::new(graph);
207 bfs.search(0);
208 assert_eq!(bfs.dist, vec![0, 1, 2, BreadthFirstSearch::INF, 3]);
209 }
210}
211
212#[derive(Debug, Clone)]
213pub struct DepthFirstSearch {
214 graph: Graph,
215 seen: Vec<bool>,
216 backptr: Vec<Option<usize>>,
217 forward_history: Vec<usize>,
218 backward_history: Vec<usize>,
219}
220
221#[derive(Debug)]
222pub enum NodeType {
223 Forward(usize),
224 Backward(usize),
225}
226
227impl DepthFirstSearch {
228 pub fn new(graph: Graph) -> Self {
229 let n = graph.n;
230 Self {
231 graph,
232 seen: vec![false; n],
233 backptr: vec![None; n],
234 forward_history: vec![],
235 backward_history: vec![],
236 }
237 }
238
239 pub fn search(&mut self, root: usize) {
240 self.dfs(root);
241 }
242
243 pub fn dfs(&mut self, u: usize) {
244 let mut stack = VecDeque::new();
245 stack.push_front(NodeType::Backward(u));
246 stack.push_front(NodeType::Forward(u));
247
248 self.seen[u] = true;
249 self.forward_history.push(u);
250
251 while let Some(node_type) = stack.pop_front() {
252 match node_type {
253 NodeType::Forward(u) => {
254 for &(v, _) in self.graph.graph[u].iter() {
255 if self.seen[v] {
256 continue;
257 }
258 stack.push_front(NodeType::Backward(v));
259 stack.push_front(NodeType::Forward(v));
260 self.backptr[v] = Some(u);
261 self.seen[v] = true;
262 self.forward_history.push(v);
263 }
264 }
265 NodeType::Backward(u) => {
266 self.backward_history.push(u);
267 }
268 }
269 }
270 }
271}
272
273#[cfg(test)]
274mod test_dfs {
275 use crate::graph::DepthFirstSearch;
276 use crate::graph::Graph;
277
278 #[test]
279 fn it_works() {
280 let mut graph = Graph::new(6, true);
281 graph.connect_unweighted(0, 1);
282 graph.connect_unweighted(1, 2);
283 graph.connect_unweighted(2, 4);
284 graph.connect_unweighted(2, 5);
285
286 let mut dfs = DepthFirstSearch::new(graph);
287 dfs.search(0);
288 assert_eq!(dfs.seen, vec![true, true, true, false, true, true]);
289 assert_eq!(dfs.backptr, vec![None, Some(0), Some(1), None, Some(2), Some(2)]);
290 assert_eq!(dfs.forward_history, vec![0, 1, 2, 4, 5]);
291 assert_eq!(dfs.backward_history, vec![5, 4, 2, 1, 0]);
292 }
293}
294
295#[derive(Debug, Clone)]
296pub struct Dijkstra {
297 source: usize,
298 graph: Graph,
299 pub dist: Vec<usize>,
300 backptrs: Vec<usize>,
301}
302
303impl Dijkstra {
304 const INF: usize = 100_000_000_000_000_000;
305
306 pub fn new(graph: Graph) -> Self {
307 let dist: Vec<usize> = vec![Self::INF; graph.n];
308 let backptrs: Vec<usize> = (0..graph.n).collect();
309 Self {
310 source: Self::INF,
311 graph,
312 dist,
313 backptrs,
314 }
315 }
316
317 pub fn search(&mut self, src: usize) {
318 self.source = src;
319
320 let mut dist = vec![Self::INF; self.graph.n];
321 dist[src] = 0;
322
323 let mut queue = std::collections::BinaryHeap::new();
324 queue.push((std::cmp::Reverse(0), src));
325
326 while let Some((std::cmp::Reverse(current_cost), current_v)) = queue.pop() {
327 for &(v, cost) in self.graph.graph[current_v].iter() {
328 if dist[v] <= current_cost + cost {
329 continue;
330 }
331 dist[v] = current_cost + cost;
332 queue.push((std::cmp::Reverse(dist[v]), v));
333 self.backptrs[v] = current_v;
334 }
335 }
336
337 self.dist = dist;
338 }
339
340 pub fn shortest_path(&self, u: usize, v: usize) -> Vec<(usize, usize)> {
341 assert_eq!(u, self.source);
342
343 if self.dist[v] == Self::INF {
344 return vec![];
345 }
346
347 let mut path = std::collections::VecDeque::new();
348
349 let mut cursor = v;
350 while cursor != u {
351 path.push_front((self.backptrs[cursor], cursor));
352 cursor = self.backptrs[cursor];
353 }
354
355 Vec::from(path)
356 }
357}
358
359#[cfg(test)]
360mod test_dijkstra {
361 use crate::graph::Dijkstra;
362 use crate::graph::Graph;
363
364 #[test]
365 fn it_works() {
366 let mut graph = Graph::new(7, true);
367 graph.connect(0, 1, 2);
368 graph.connect(0, 2, 5);
369 graph.connect(1, 2, 4);
370 graph.connect(1, 3, 5);
371 graph.connect(1, 4, 10);
372 graph.connect(2, 3, 2);
373 graph.connect(3, 5, 1);
374 graph.connect(4, 5, 5);
375 graph.connect(4, 6, 5);
376 graph.connect(5, 6, 10);
377
378 let mut dijkstra = Dijkstra::new(graph);
379 dijkstra.search(0);
380 assert_eq!(dijkstra.dist, vec![0, 2, 5, 7, 12, 8, 17]);
381
382 let expected = vec![(0, 1), (1, 4), (4, 6)];
383 assert_eq!(dijkstra.shortest_path(0, 6), expected);
384 }
385
386 #[test]
387 fn it_works_unreachable_path() {
388 let mut graph = Graph::new(9, true);
389 graph.connect(0, 1, 1);
390 graph.connect(0, 6, 10);
391 graph.connect(1, 2, 5);
392 graph.connect(1, 3, 2);
393 graph.connect(3, 4, 2);
394 graph.connect(4, 5, 3);
395 graph.connect(5, 6, 3);
396 graph.connect(7, 0, 1);
397 graph.connect(8, 7, 2);
398
399 let mut dijkstra = Dijkstra::new(graph);
400 dijkstra.search(0);
401 assert_eq!(dijkstra.dist, vec![0, 1, 6, 3, 5, 8, 10, Dijkstra::INF, Dijkstra::INF]);
402
403 assert_eq!(dijkstra.shortest_path(0, 3), vec![(0, 1), (1, 3)]);
404 assert_eq!(dijkstra.shortest_path(0, 8), vec![]);
405 }
406}
407
408pub struct EulerTour {
409 graph: Graph,
410 l: Vec<usize>,
411 r: Vec<usize>,
412 t: usize,
413}
414
415impl EulerTour {
416 const INF: usize = 100_000_000_000_000_000;
417
418 pub fn new(n: usize, graph: Graph) -> Self {
419 let l = vec![Self::INF; n];
420 let r = vec![Self::INF; n];
421 Self { graph, l, r, t: 1 }
422 }
423
424 pub fn traverse(&mut self, root: usize) -> (&[usize], &[usize]) {
430 self._dfs(root, None);
431
432 for i in 0..self.l.len() {
433 if self.r[i] == Self::INF {
434 self.r[i] = self.l[i];
435 }
436 }
437
438 (&self.l, &self.r)
439 }
440
441 fn _dfs(&mut self, u: usize, p: Option<usize>) {
442 self.l[u] = self.t;
443 self.t += 1;
444
445 for i in 0..self.graph.graph[u].len() {
446 let (v, _) = self.graph.graph[u][i];
447 if p != Some(v) {
448 self._dfs(v, Some(u));
449 self.r[u] = self.t;
450 self.t += 1;
451 }
452 }
453 }
454}
455
456#[cfg(test)]
457mod test_euler_tour {
458 use crate::graph::EulerTour;
459 use crate::graph::Graph;
460
461 #[test]
462 fn it_works() {
463 let mut graph = Graph::new(7, false);
464 graph.connect_unweighted(0, 1);
465 graph.connect_unweighted(1, 2);
466 graph.connect_unweighted(1, 3);
467 graph.connect_unweighted(3, 4);
468 graph.connect_unweighted(0, 5);
469 graph.connect_unweighted(5, 6);
470
471 let mut euler_tour = EulerTour::new(7, graph);
472 let (l, r) = euler_tour.traverse(0);
473
474 assert_eq!(l, &vec![1, 2, 3, 5, 6, 10, 11]);
475 assert_eq!(r, &vec![13, 8, 3, 7, 6, 12, 11]);
476 }
477}
478
479pub struct FordFullkerson {
480 pub graph: Graph,
481 pub used: Vec<bool>,
482 pub flow: usize,
483}
484
485impl FordFullkerson {
486 const INF: usize = 100_000_000_000_000_000;
487
488 pub fn new(graph: Graph) -> Self {
489 let used = vec![false; graph.n];
490 let flow = Self::INF;
491 Self { graph, used, flow }
492 }
493
494 pub fn dfs(&mut self, u: usize, t: usize, f: usize) -> usize {
495 if u == t {
496 return f;
497 }
498
499 self.used[u] = true;
500 for i in 0..self.graph.graph[u].len() {
501 let (v, cap) = self.graph.graph[u][i];
502 let r = self.graph.rev[u][i];
503 if !self.used[v] && cap > 0 {
504 let d = self.dfs(v, t, f.min(cap));
505
506 if d > 0 {
507 self.graph.graph[u][i].1 -= d;
508 self.graph.graph[v][r].1 += d;
509 return d;
510 }
511 }
512 }
513
514 0
515 }
516
517 pub fn solve(&mut self, s: usize, t: usize) -> usize {
518 let mut flow = 0;
519 loop {
520 self.used = vec![false; self.graph.n];
521 let f: usize = self.dfs(s, t, FordFullkerson::INF);
522 if f == 0 {
523 return flow;
524 }
525 flow += f;
526 }
527 }
528}
529
530#[cfg(test)]
531mod test_ford_fullkerson {
532 use crate::graph::FordFullkerson;
533 use crate::graph::Graph;
534
535 #[test]
536 fn it_works() {
537 let mut graph = Graph::new(4, true);
538 graph.connect_with_residual(0, 1, 2);
539 graph.connect_with_residual(0, 2, 1);
540 graph.connect_with_residual(1, 2, 1);
541 graph.connect_with_residual(1, 3, 1);
542 graph.connect_with_residual(2, 3, 2);
543
544 let mut solver = FordFullkerson::new(graph);
545 let maxflow = solver.solve(0, 3);
546 assert_eq!(maxflow, 3);
547 }
548}
549
550pub struct LowestCommonAncestor {
551 parents: Vec<Vec<usize>>,
552 depth: Vec<usize>,
553 graph: Graph,
554}
555
556impl LowestCommonAncestor {
557 const ROOT: usize = 0;
558 const LOGV: usize = 30;
559
560 pub fn new(graph: Graph) -> Self {
561 let n = graph.n;
562 let parents = vec![vec![Self::ROOT; n]; Self::LOGV];
563 let depth = vec![Self::ROOT; n];
564 Self { parents, depth, graph }
565 }
566
567 pub fn init(&mut self) {
568 self.dfs(Self::ROOT);
569
570 for k in 0..Self::LOGV - 1 {
571 for v in 0..self.graph.n {
572 self.parents[k + 1][v] = self.parents[k][self.parents[k][v]];
573 }
574 }
575 }
576
577 fn dfs(&mut self, u: usize) {
578 let mut stack = VecDeque::new();
579 self.parents[0][u] = u;
580 self.depth[u] = 0;
581 stack.push_front((u, u, 1));
582
583 while let Some((u, p, d)) = stack.pop_front() {
584 for &(v, _) in self.graph.graph[u].iter() {
585 if v == p {
586 continue;
587 }
588 self.parents[0][v] = u;
589 self.depth[v] = d + 1;
590 stack.push_front((v, u, d + 1));
591 }
592 }
593 }
594
595 pub fn lca(&self, mut u: usize, mut v: usize) -> usize {
596 if self.depth[u] > self.depth[v] {
597 std::mem::swap(&mut u, &mut v);
598 }
599
600 for k in 0..Self::LOGV {
601 if (((self.depth[v] - self.depth[u]) >> k) & 1) == 1 {
602 v = self.parents[k][v];
603 }
604 }
605
606 if u == v {
607 return u;
608 }
609
610 for k in (0..Self::LOGV).rev() {
611 if self.parents[k][u] != self.parents[k][v] {
612 u = self.parents[k][u];
613 v = self.parents[k][v];
614 }
615 }
616
617 self.parents[0][u]
618 }
619}
620
621#[cfg(test)]
622mod test_lca {
623 use crate::graph::Graph;
624 use crate::graph::LowestCommonAncestor;
625
626 #[test]
627 fn it_works() {
628 let mut graph = Graph::new(8, false);
629 graph.connect_unweighted(0, 1);
630 graph.connect_unweighted(0, 2);
631 graph.connect_unweighted(1, 3);
632 graph.connect_unweighted(1, 4);
633 graph.connect_unweighted(2, 5);
634 graph.connect_unweighted(2, 6);
635 graph.connect_unweighted(3, 7);
636
637 let mut lca = LowestCommonAncestor::new(graph);
638 lca.init();
639
640 assert_eq!(lca.lca(0, 1), 0);
641 assert_eq!(lca.lca(7, 4), 1);
642 assert_eq!(lca.lca(1, 4), 1);
643 assert_eq!(lca.lca(4, 1), 1);
644 assert_eq!(lca.lca(7, 6), 0);
645 assert_eq!(lca.lca(5, 6), 2);
646 assert_eq!(lca.lca(3, 5), 0);
647 }
648
649 #[test]
650 fn it_works_line() {
651 let mut graph = Graph::new(5, false);
652 graph.connect_unweighted(0, 1);
653 graph.connect_unweighted(1, 2);
654 graph.connect_unweighted(2, 3);
655 graph.connect_unweighted(3, 4);
656
657 let mut lca = LowestCommonAncestor::new(graph);
658 lca.init();
659
660 assert_eq!(lca.lca(0, 0), 0);
661 assert_eq!(lca.lca(0, 1), 0);
662 assert_eq!(lca.lca(0, 2), 0);
663 assert_eq!(lca.lca(0, 3), 0);
664 assert_eq!(lca.lca(1, 4), 1);
665 assert_eq!(lca.lca(4, 1), 1);
666 }
667}
668
669#[derive(Debug, Clone)]
670pub struct Lowlink {
671 graph: Graph,
672 used: Vec<bool>,
673 ord: Vec<usize>,
674 low: Vec<usize>,
675 bridges: Vec<(usize, usize)>,
676}
677
678#[allow(clippy::needless_range_loop)]
679impl Lowlink {
680 pub fn new(graph: Graph) -> Self {
681 let n: usize = graph.n;
682 let used = vec![false; n];
683 let ord: Vec<usize> = vec![0; n];
684 let low: Vec<usize> = vec![0; n];
685 let bridges: Vec<(usize, usize)> = vec![];
686
687 Self {
688 graph,
689 used,
690 ord,
691 low,
692 bridges,
693 }
694 }
695
696 pub fn search(&mut self) {
697 let mut k = 0;
698 for u in 0..self.graph.n {
699 if self.used[u] {
700 continue;
701 }
702 k = self.dfs(u, k, None);
703 }
704 }
705
706 pub fn dfs(&mut self, u: usize, mut k: usize, p: Option<usize>) -> usize {
707 self.used[u] = true;
708
709 self.ord[u] = k;
710 self.low[u] = k;
711 k += 1;
712
713 for i in 0..self.graph.graph[u].len() {
714 let (v, _) = self.graph.graph[u][i];
715
716 if !self.used[v] {
717 k = self.dfs(v, k, Some(u));
718 self.low[u] = self.low[u].min(self.low[v]);
719
720 if self.ord[u] < self.low[v] {
721 self.bridges.push((u.min(v), u.max(v)));
722 }
723 } else if p.is_some() && v != p.unwrap() {
724 self.low[u] = self.low[u].min(self.ord[v]);
725 }
726 }
727
728 k
729 }
730
731 pub fn num_bridges(&self) -> usize {
732 self.bridges.len()
733 }
734}
735
736#[cfg(test)]
737mod test_lowlink {
738 use crate::graph::Graph;
739 use crate::graph::Lowlink;
740
741 #[test]
742 fn it_works() {
743 let mut graph = Graph::new(7, false);
744 graph.connect_unweighted(0, 2);
745 graph.connect_unweighted(1, 6);
746 graph.connect_unweighted(2, 3);
747 graph.connect_unweighted(3, 4);
748 graph.connect_unweighted(3, 5);
749 graph.connect_unweighted(4, 5);
750 graph.connect_unweighted(5, 6);
751
752 let mut lowlink = Lowlink::new(graph);
753 lowlink.search();
754
755 assert_eq!(lowlink.ord, vec![0, 6, 1, 2, 3, 4, 5]);
756 assert_eq!(lowlink.low, vec![0, 6, 1, 2, 2, 2, 5]);
757 assert_eq!(lowlink.num_bridges(), 4);
758 }
759
760 #[test]
761 fn it_works_without_bridge() {
762 let mut graph = Graph::new(3, false);
763 graph.connect_unweighted(0, 1);
764 graph.connect_unweighted(0, 2);
765 graph.connect_unweighted(1, 2);
766
767 let mut lowlink = Lowlink::new(graph);
768 lowlink.search();
769
770 assert_eq!(lowlink.ord, vec![0, 1, 2]);
771 assert_eq!(lowlink.low, vec![0, 0, 0]);
772 assert_eq!(lowlink.num_bridges(), 0);
773 }
774
775 #[test]
776 fn it_works_with_all_edges_are_bridges() {
777 let mut graph = Graph::new(6, false);
778 graph.connect_unweighted(0, 1);
779 graph.connect_unweighted(1, 2);
780 graph.connect_unweighted(2, 3);
781 graph.connect_unweighted(3, 4);
782 graph.connect_unweighted(4, 5);
783
784 let mut lowlink = Lowlink::new(graph);
785 lowlink.search();
786
787 assert_eq!(lowlink.ord, vec![0, 1, 2, 3, 4, 5]);
788 assert_eq!(lowlink.low, vec![0, 1, 2, 3, 4, 5]);
789 assert_eq!(lowlink.num_bridges(), 5);
790 }
791
792 #[test]
793 fn it_works_hand() {
794 let mut graph = Graph::new(7, false);
795 graph.connect_unweighted(0, 1);
796 graph.connect_unweighted(1, 2);
797 graph.connect_unweighted(1, 3);
798 graph.connect_unweighted(2, 4);
799 graph.connect_unweighted(4, 5);
800 graph.connect_unweighted(4, 6);
801 graph.connect_unweighted(5, 6);
802
803 let mut lowlink = Lowlink::new(graph);
804 lowlink.search();
805
806 assert_eq!(lowlink.ord, vec![0, 1, 2, 6, 3, 4, 5]);
807 assert_eq!(lowlink.low, vec![0, 1, 2, 6, 3, 3, 3]);
808 assert_eq!(lowlink.num_bridges(), 4);
809 }
810}
811
812pub struct StronglyConnectedComponent {
813 forward_graph: Graph,
814 forward_visited: Vec<bool>,
815 forward_visited_nodes: VecDeque<usize>,
816 backward_graph: Graph,
817 backward_visited: Vec<bool>,
818 topological_ranks: Vec<usize>,
819}
820
821impl StronglyConnectedComponent {
822 pub fn new(graph: Graph) -> Self {
823 let n = graph.n;
824 let forward_graph = graph;
825 let mut backward_graph = Graph::new(n, true);
826
827 for u in 0..n {
828 for &(v, _) in forward_graph.graph[u].iter() {
829 backward_graph.connect_unweighted(v, u);
830 }
831 }
832
833 Self {
834 forward_graph,
835 forward_visited: vec![false; n],
836 forward_visited_nodes: VecDeque::new(),
837 backward_graph,
838 backward_visited: vec![false; n],
839 topological_ranks: vec![0; n],
840 }
841 }
842
843 pub fn scc(&mut self) -> usize {
844 for u in 0..self.forward_graph.n {
845 if self.forward_visited[u] {
846 continue;
847 }
848
849 self.fdfs(u);
850 }
851
852 let mut topological_rank = 0;
853 while let Some(u) = self.forward_visited_nodes.pop_back() {
854 if self.backward_visited[u] {
855 continue;
856 }
857
858 self.rdfs(u, topological_rank);
859 topological_rank += 1;
860 }
861
862 topological_rank
863 }
864
865 fn fdfs(&mut self, u: usize) {
866 self.forward_visited[u] = true;
867
868 for i in 0..self.forward_graph.graph[u].len() {
869 let (v, _) = self.forward_graph.graph[u][i];
870
871 if self.forward_visited[v] {
872 continue;
873 }
874
875 self.fdfs(v);
876 }
877
878 self.forward_visited_nodes.push_back(u);
879 }
880
881 fn rdfs(&mut self, u: usize, topological_rank: usize) {
882 self.backward_visited[u] = true;
883 self.topological_ranks[u] = topological_rank;
884
885 for i in 0..self.backward_graph.graph[u].len() {
886 let (v, _) = self.backward_graph.graph[u][i];
887
888 if self.backward_visited[v] {
889 continue;
890 }
891
892 self.rdfs(v, topological_rank);
893 }
894 }
895}
896
897#[cfg(test)]
898mod test_scc {
899 use crate::graph::Graph;
900 use crate::graph::StronglyConnectedComponent;
901
902 #[test]
903 fn it_works() {
904 let mut graph = Graph::new(6, true);
905 graph.connect_unweighted(1, 4);
906 graph.connect_unweighted(5, 2);
907 graph.connect_unweighted(3, 0);
908 graph.connect_unweighted(5, 5);
909 graph.connect_unweighted(4, 1);
910 graph.connect_unweighted(0, 3);
911 graph.connect_unweighted(4, 2);
912
913 let mut scc = StronglyConnectedComponent::new(graph);
914 assert_eq!(scc.scc(), 4);
915 assert_eq!(scc.topological_ranks, vec![3, 1, 2, 3, 1, 0]);
916 }
917}
918
919pub struct TopologicalSort {
920 graph: Graph,
921}
922
923#[allow(clippy::needless_range_loop)]
924impl TopologicalSort {
925 pub fn new(graph: Graph) -> Self {
926 Self { graph }
927 }
928
929 pub fn sort(&mut self) -> Vec<usize> {
930 let mut ans: Vec<usize> = vec![];
931 let mut s = std::collections::BinaryHeap::new();
932 let mut degrees = self.graph.in_degrees.clone();
933
934 for v in 0..self.graph.n {
935 if degrees[v] == 0 {
936 s.push(std::cmp::Reverse(v));
937 }
938 }
939
940 while let Some(std::cmp::Reverse(v)) = s.pop() {
941 ans.push(v);
942
943 for &(nv, _) in self.graph.graph[v].iter() {
944 if degrees[nv] == 0 {
945 continue;
946 }
947
948 degrees[nv] -= 1;
949
950 if degrees[nv] == 0 {
951 s.push(std::cmp::Reverse(nv));
952 }
953 }
954 }
955
956 if ans.len() == self.graph.n {
957 ans
958 } else {
959 vec![]
960 }
961 }
962}
963
964#[cfg(test)]
965mod test_topological_sort {
966 use crate::graph::Graph;
967 use crate::graph::TopologicalSort;
968
969 #[test]
970 fn it_works() {
971 let mut graph = Graph::new(4, true);
972 graph.connect_unweighted(1, 0);
973 graph.connect_unweighted(1, 3);
974 graph.connect_unweighted(2, 3);
975
976 let mut sorter = TopologicalSort::new(graph);
977 assert_eq!(sorter.sort(), vec![1, 0, 2, 3]);
978 }
979
980 #[test]
981 fn it_works_circle() {
982 let mut graph = Graph::new(2, false);
983 graph.connect_unweighted(0, 1);
984
985 let mut sorter = TopologicalSort::new(graph);
986 assert_eq!(sorter.sort(), vec![]);
987 }
988}