cp_library_rs/graph/
scc.rs

1//! 強連結成分分解
2
3type Graph = Vec<Vec<usize>>;
4
5/// ## SCC (強連結成分分解)
6/// - Strongly Conneected Components
7#[derive(Debug)]
8pub struct SCC {
9    pub V: usize,
10    pub E: usize,
11    pub G: Graph,
12    rG: Graph,
13    pub group_count: Option<usize>,
14    pub belongs_to: Option<Vec<usize>>,
15    pub components: Option<Vec<Vec<usize>>>,
16    pub DAG: Option<Graph>,
17}
18
19impl SCC {
20    const INF: usize = usize::MAX;
21
22    /// 頂点`V`のグラフを構築する
23    pub fn new(N: usize) -> Self {
24        Self {
25            V: N,
26            E: 0,
27            G: vec![vec![]; N],
28            rG: vec![vec![]; N],
29            group_count: None,
30            belongs_to: None,
31            components: None,
32            DAG: None,
33        }
34    }
35
36    /// uからvへの有向辺を追加
37    pub fn add_edge(&mut self, u: usize, v: usize) {
38        self.E += 1;
39        self.G[u].push(v);
40        self.rG[v].push(u);
41    }
42
43    /// 強連結成分に分解する
44    pub fn decompose(&mut self) {
45        // 帰りがけ順で順序付け
46        let mut order = vec![];
47        let mut visited = vec![false; self.V];
48        for i in 0..self.V {
49            Self::dfs(i, &self.G, &mut order, &mut visited);
50        }
51
52        // 連結成分に分解
53        let mut group = 0;
54        let mut belongs_to = vec![Self::INF; self.V];
55        for &i in order.iter().rev() {
56            if belongs_to[i] == Self::INF {
57                Self::rdfs(i, group, &self.rG, &mut belongs_to);
58                group += 1;
59            }
60        }
61
62        // DAGを構築
63        let mut DAG = vec![vec![]; group];
64        for i in 0..self.V {
65            for &j in &self.G[i] {
66                let (u, v) = (belongs_to[i], belongs_to[j]);
67                if u != v {
68                    DAG[u].push(v);
69                }
70            }
71        }
72
73        // 分解する
74        self.components = Some(belongs_to.iter().enumerate().fold(
75            vec![vec![]; group],
76            |mut components, (v, &g)| {
77                components[g].push(v);
78                components
79            },
80        ));
81        self.group_count = Some(group);
82        self.belongs_to = Some(belongs_to);
83        self.DAG = Some(DAG);
84    }
85
86    fn dfs(u: usize, G: &Graph, order: &mut Vec<usize>, visited: &mut Vec<bool>) {
87        if visited[u] {
88            return;
89        }
90        visited[u] = true;
91        for &v in &G[u] {
92            Self::dfs(v, G, order, visited);
93        }
94        order.push(u);
95    }
96
97    fn rdfs(u: usize, group: usize, rG: &Graph, belongs_to: &mut Vec<usize>) {
98        if belongs_to[u] != Self::INF {
99            return;
100        }
101        belongs_to[u] = group;
102        for &v in &rG[u] {
103            Self::rdfs(v, group, rG, belongs_to);
104        }
105    }
106}
cp_library_rs/graph/scc.rs

cp_library_rs/graph/
scc.rs
