AtCoder Beginner Contest 315 E

https://atcoder.jp/contests/abc315/tasks/abc315_e

トポロジカルソートですね。1から辿れるノードを集めて、そのノードだけで逆向きのグラフを作って、トポロジカルソートです。

// Prerequisites
#![allow(non_snake_case)]

use std::collections::{HashSet, HashMap};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Graph ////////////////////

type Node = usize;
type Graph = HashMap<Node, Vec<Node>>;

fn create_graph(edges: Vec<Vec<Node>>) -> Graph {
    let N = edges.len();
    let mut graph: Graph = (0..N).map(|v| (v, vec![])).collect();
    for (i, vs) in edges.into_iter().enumerate() {
        graph.insert(i, vs);
    }
    graph
}

fn reverse_graph(graph: &Graph) -> Graph {
    let mut rev_graph: Graph = graph.keys().map(|&v| (v, vec![])).collect();
    for (&u, vs) in graph.iter() {
        for &v in vs.iter() {
            let e = rev_graph.entry(v).or_insert(vec![]);
            (*e).push(u)
        }
    }
    rev_graph
}

fn walk(v0: Node, graph: &Graph) -> Vec<Node> {
    let mut visited: HashSet<Node> = HashSet::new();
    visited.insert(v0);
    let mut stack: Vec<Node> = vec![v0];
    while !stack.is_empty() {
        let v = stack.pop().unwrap();
        match graph.get(&v) {
            Some(vs) => {
                for &v1 in vs.iter() {
                    if !visited.contains(&v1) {
                        stack.push(v1+0);
                        visited.insert(v1);
                    }
                }
            },
            None     => ()
        }
    }
    visited.into_iter().collect::<Vec<Node>>()
}

fn collect_indegrees(graph: &Graph) -> HashMap<Node, i32> {
    let mut ds: HashMap<Node, i32> = graph.keys().map(|&u| (u, 0)).collect();
    for (_, vs) in graph.iter() {
        for &v in vs.iter() {
            let e = ds.entry(v).or_insert(0);
            *e += 1
        }
    }
    ds
}

fn sort_topologically(graph: &Graph) -> Vec<Node> {
    let mut ds = collect_indegrees(graph);
    let mut queue = std::collections::VecDeque::new();
    for (&v, &d) in ds.iter() {
        if d == 0 {
            queue.push_back(v)
        }
    }
    
    let mut sorted_nodes: Vec<Node> = Vec::new();
    while let Some(v) = queue.pop_front() {
        sorted_nodes.push(v);
        let ws = graph.get(&v).unwrap();
        for &w in ws.iter() {
            let e = ds.entry(w).or_insert(0);
            *e -= 1;
            if *e == 0 {
                queue.push_back(w)
            }
        }
    }
    sorted_nodes
}


//////////////////// process ////////////////////

fn read_input() -> Vec<Vec<Node>> {
    let N: usize = read();
    (0..N).map(|_| read_vec::<usize>()).
            map(|v| (1..v.len()).map(|i| v[i]-1).collect::<Vec<Node>>()).
            collect::<Vec<Vec<Node>>>()
}

fn extract_graph(graph: &Graph, vs: Vec<Node>) -> Graph {
    let mut subg: Graph = Graph::new();
    let set_vs: HashSet<Node> = vs.iter().map(|&v| v).collect();
    for v in vs.into_iter() {
        match graph.get(&v) {
            Some(vs1) => {
                let vs2: Vec<Node> = vs1.iter().map(|&v2| v2).
                                        filter(|v2| set_vs.contains(v2)).
                                        collect();
                subg.insert(v, vs2);
            },
            None => ()
        }
    }
    subg
}

fn f(edges_: Vec<Vec<Node>>) -> String {
    let edges = edges_.iter().map(|v| v.iter().filter(|&u| *u != 0).
                                        map(|u| *u).collect::<Vec<Node>>()).
                collect::<Vec<Vec<Node>>>();
    let graph = create_graph(edges);
    let rev_graph = reverse_graph(&graph);
    let vs = walk(0, &graph);
    let subg = extract_graph(&rev_graph, vs);
    let nodes = sort_topologically(&subg);
    let ss: Vec<String> = nodes[..nodes.len()-1].iter().
                                map(|v| (v+1).to_string()).collect();
    ss.join(" ")
}


//////////////////// main ////////////////////

fn main() {
    let pairs = read_input();
    println!("{}", f(pairs))
}