graph/topological-sort/src/lib.rs

• View this file on GitHub
• Last update: 2025-04-18 21:05:47+09:00

Code

use std::{cmp::Reverse, collections::BinaryHeap};

#[derive(Debug, Clone)]
pub struct TopologicalSort {
    size: usize,
    graph: Vec<Vec<usize>>,
}

impl TopologicalSort {
    pub fn new(size: usize) -> Self {
        Self {
            size,
            graph: vec![vec![]; size],
        }
    }

    pub fn add_edge(&mut self, from: usize, to: usize) {
        self.graph[from].push(to);
    }

    pub fn topological_sort(&mut self) -> Vec<usize> {
        let mut indegree = vec![0; self.size];
        for from in 0..self.size {
            for i in 0..self.graph[from].len() {
                let to = self.graph[from][i];
                indegree[to] += 1;
            }
        }
        let mut heap = BinaryHeap::new();
        for from in 0..self.size {
            if indegree[from] == 0 {
                heap.push(Reverse(from));
            }
        }
        let mut res = vec![];
        while let Some(Reverse(from)) = heap.pop() {
            res.push(from);
            for i in 0..self.graph[from].len() {
                let to = self.graph[from][i];
                indegree[to] -= 1;
                if indegree[to] == 0 {
                    heap.push(Reverse(to));
                }
            }
        }
        if res.len() != self.size {
            return vec![];
        }
        res
    }
}

pub fn topological_sort(size: usize, graph: &Vec<Vec<usize>>) -> Vec<usize> {
    let mut indegree = vec![0; size];
    for from in 0..size {
        for i in 0..graph[from].len() {
            let to = graph[from][i];
            indegree[to] += 1;
        }
    }
    let mut heap = BinaryHeap::new();
    for from in 0..size {
        if indegree[from] == 0 {
            heap.push(Reverse(from));
        }
    }
    let mut res = vec![];
    while let Some(Reverse(from)) = heap.pop() {
        res.push(from);
        for i in 0..graph[from].len() {
            let to = graph[from][i];
            indegree[to] -= 1;
            if indegree[to] == 0 {
                heap.push(Reverse(to));
            }
        }
    }
    if res.len() != size {
        return vec![];
    }
    res
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page