AtCoder Beginner Contest 456 E

https://atcoder.jp/contests/abc456/tasks/abc456_e

都市と曜日の組み合わせをノードにして有向グラフにして、ループがあるかを判定します。

// Endless Holidays
#![allow(non_snake_case)]


//////////////////// 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()
}

fn YesNo(b: bool) -> String {
    return if b { "Yes" } else { "No" }.to_string()
}


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

type Node = usize;
type Edge = (Node, Node);

fn read_edge() -> Edge {
    let v: Vec<usize> = read_vec();
    let (U, V) = (v[0]-1, v[1]-1);
    (U, V)
}

struct Graph {
    g: Vec<Vec<Node>>
}

impl Graph {
    fn find_loop_core(&self, v: Node, v0: Node,
                                visited: &mut Vec<Node>) -> bool {
        for &v1 in self.g[v].iter() {
            if visited[v1] == v0 + 1 {
                return true
            }
            else if visited[v1] == usize::MAX {
                visited[v1] = v0 + 1;
                if self.find_loop_core(v1, v0, visited) {
                    return true
                }
                visited[v1] = v0
            }
        }
        false
    }
    
    fn find_loop(&self, v0: Node, visited: &mut Vec<Node>) -> bool {
        // 今辿っているpathならv0+1とする
        // ループがなければv0にする
        visited[v0] = v0 + 1;
        if self.find_loop_core(v0, v0, visited) {
            true
        }
        else {
            visited[v0] = v0;
            false
        }
    }
    
    fn has_loop(&self) -> bool {
        let N = self.g.len();
        let mut visited: Vec<Node> = vec![usize::MAX; N];
        for v in 0..N {
            if visited[v] != usize::MAX {
                continue
            }
            if self.find_loop(v, &mut visited) {
                return true
            }
        }
        false
    }
}


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

use std::collections::HashSet;

fn read_case() -> (Vec<Edge>, Vec<String>) {
    let v: Vec<usize> = read_vec();
    let (N, M) = (v[0], v[1]);
    let edges_: HashSet<Edge> = (0..M).map(|_| read_edge()).collect();
    let edges: Vec<Edge> = edges_.into_iter().collect();
    let _W: usize = read();
    let S: Vec<String> = (0..N).map(|_| read::<String>()).collect();
    (edges, S)
}

fn create_graph(edges: Vec<Edge>, bss: Vec<Vec<bool>>) -> Graph {
    let N = bss.len();
    let W = bss[0].len();
    let mut g: Vec<Vec<Node>> = vec![vec![]; N*W];
    for (U, V) in edges {
        for i in 0..W {
            let j = (i + 1) % W;
            if bss[U][i] && bss[V][j] {
                g[U*W+i].push(V*W+j)
            }
            if bss[V][i] && bss[U][j] {
                g[V*W+i].push(U*W+j)
            }
        }
    }
    
    // 同じ都市に留まる
    for v in 0..N {
        for i in 0..W {
            let j = (i + 1) % W;
            if bss[v][i] && bss[v][j] {
                g[v*W+i].push(v*W+j)
            }
        }
    }
    
    Graph { g }
}

fn F_each(edges: Vec<Edge>, S: Vec<String>) -> bool {
    let bss: Vec<Vec<bool>> = S.iter().map(|s| s.chars().map(|c| c =='o').
                                                collect::<Vec<_>>()).collect();
    let graph = create_graph(edges, bss);
    graph.has_loop()
}

fn F(T: usize) {
    for _ in 0..T {
        let (edges, S) = read_case();
        println!("{}", YesNo(F_each(edges, S)))
    }
}

fn main() {
    let T: usize = read();
    F(T)
}