dsalgo/
connected_components_dfs.rs

1pub fn connected_components(g: &[Vec<usize>]) -> Vec<usize> {
2    let n = g.len();
3
4    let mut ids = vec![n; n];
5
6    let mut id = 0;
7
8    let mut st = vec![];
9
10    for i in 0..n {
11        if ids[i] != n {
12            continue;
13        }
14
15        st.push(i);
16
17        while let Some(u) = st.pop() {
18            if ids[u] != n {
19                continue;
20            }
21
22            ids[u] = id;
23
24            for &v in g[u].iter() {
25                if ids[v] == n {
26                    st.push(v);
27                }
28            }
29        }
30
31        id += 1;
32    }
33
34    ids
35}