結果

問題 No.1605 Matrix Shape
ユーザー atcoder8atcoder8
提出日時 2023-04-16 14:52:22
言語 Rust
(1.77.0)
結果
AC  
実行時間 116 ms / 2,000 ms
コード長 17,516 bytes
コンパイル時間 2,878 ms
コンパイル使用メモリ 178,776 KB
実行使用メモリ 23,868 KB
最終ジャッジ日時 2024-04-20 04:48:40
合計ジャッジ時間 4,439 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 0 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 0 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 0 ms
6,944 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 1 ms
6,944 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 1 ms
6,944 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 1 ms
6,944 KB
testcase_18 AC 0 ms
6,944 KB
testcase_19 AC 116 ms
23,832 KB
testcase_20 AC 101 ms
21,452 KB
testcase_21 AC 94 ms
19,928 KB
testcase_22 AC 108 ms
22,352 KB
testcase_23 AC 113 ms
23,868 KB
testcase_24 AC 107 ms
22,300 KB
testcase_25 AC 60 ms
18,984 KB
testcase_26 AC 59 ms
19,204 KB
testcase_27 AC 54 ms
17,616 KB
testcase_28 AC 54 ms
17,564 KB
testcase_29 AC 54 ms
17,464 KB
testcase_30 AC 113 ms
21,500 KB
testcase_31 AC 95 ms
19,896 KB
testcase_32 AC 93 ms
20,172 KB
testcase_33 AC 85 ms
18,600 KB
testcase_34 AC 35 ms
18,564 KB
testcase_35 AC 80 ms
18,220 KB
testcase_36 AC 50 ms
12,032 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use atcoder8_library::union_find::UnionFind;

fn main() {
    let n = {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse::<usize>().unwrap()
    };
    let mut hw = Vec::new();
    for _ in 0..n {
        hw.push({
            let mut line = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                iter.next().unwrap().parse::<usize>().unwrap() - 1,
                iter.next().unwrap().parse::<usize>().unwrap() - 1,
            )
        });
    }

    let values: Vec<usize> = hw
        .iter()
        .map(|x| x.0)
        .chain(hw.iter().map(|x| x.1))
        .collect();
    let (zip, unzip) = coordinate_compression(&values);

    let zip_hw: Vec<(usize, usize)> = (0..n).map(|i| (zip[i], zip[n + i])).collect();

    let node_num = unzip.len();

    let mut uf = UnionFind::new(node_num);

    let mut indegree = vec![0; node_num];
    let mut outdegree = vec![0; node_num];
    for &(h, w) in &zip_hw {
        indegree[w] += 1;
        outdegree[h] += 1;

        uf.merge(h, w);
    }

    if uf.group_num() != 1 {
        println!("0");
        std::process::exit(0);
    }

    let same_num = (0..node_num)
        .filter(|&i| indegree[i] == outdegree[i])
        .count();

    if same_num == node_num {
        let mut ww: Vec<usize> = hw.iter().map(|x| x.1).collect();
        ww.sort_unstable();
        ww.dedup();
        println!("{}", ww.len());
    } else if same_num == node_num - 2
        && (0..node_num)
            .filter(|&i| indegree[i] + 1 == outdegree[i])
            .count()
            == 1
        && (0..node_num)
            .filter(|&i| indegree[i] == outdegree[i] + 1)
            .count()
            == 1
    {
        println!("1");
    } else {
        println!("0");
    }
}

/// Performs coordinate compression of `seq`.
///
/// The return value is a tuple of `zip` and `unzip`.
/// `zip` is a list of the number of smallest values in the whole sequence for each element.
/// `unzip` is a list of the values that appear in the number sequence in ascending order.
/// The `i`-th element of the original sequence can be restored by `unzip[zip[i]]`.
pub fn coordinate_compression<T>(seq: &[T]) -> (Vec<usize>, Vec<T>)
where
    T: Clone + Ord,
{
    let mut unzip = seq.to_owned();
    unzip.sort_unstable();
    unzip.dedup();

    let zip: Vec<usize> = seq
        .iter()
        .map(|x| unzip.binary_search(x).unwrap())
        .collect();

    (zip, unzip)
}

pub mod atcoder8_library {
    pub mod union_find {
        //! Union-Find processes the following queries on undirected graphs.
        //! * Merge two connected components.
        //! * Determine whether two given nodes are in the same connected component.
        //!
        //! To seed up processing, merge optimization using the number of nodes
        //! of the connected components and path compression are performed.
        //!
        //! The time complexity of each query is `O(A(n))`.
        //! where `n` is the number of nodes in the graph and
        //! `A(n)` is the inverse of the Ackermann function.

        /// This is the value that will be associated with each nodes of the graph.
        #[derive(Debug, Clone, Copy)]
        enum ParentOrSize {
            /// It is used for non-representative nodes and stores the parent node.
            Parent(usize),

            /// It is used for the representative node and
            /// stores the number of nodes of the connected component.
            Size(usize),
        }

        /// Union-Find processes the following queries on undirected graphs.
        /// * Merge two connected components.
        /// * Determine whether two given nodes are in the same connected component.
        ///
        /// To seed up processing, merge optimization using the number of nodes
        /// of the connected components and path compression are performed.
        ///
        /// The time complexity of each query is `O(A(n))`.
        /// where `n` is the number of nodes in the graph and
        /// `A(n)` is the inverse of the Ackermann function.
        ///
        /// # Examples
        ///
        /// ```
        /// use atcoder8_library::union_find::UnionFind;
        ///
        /// let mut uf = UnionFind::new(3);
        /// assert_eq!(uf.same(0, 2), false);
        /// uf.merge(0, 1);
        /// assert_eq!(uf.same(0, 2), false);
        /// uf.merge(1, 2);
        /// assert_eq!(uf.same(0, 2), true);
        /// ```
        #[derive(Debug, Default, Clone)]
        pub struct UnionFind {
            /// For each node, one of the following is stored.
            /// * The number of nodes of the connected component to which it belongs.
            /// (If it is a representative node of the connected component.)
            /// * Index of the parent node. (Otherwise.)
            parent_or_size: Vec<ParentOrSize>,

            /// Number of connected components.
            group_num: usize,
        }

        impl UnionFind {
            /// Create an undirected graph with `n` nodes and `0` edges.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(0, 1);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(2, 1);
            /// assert_eq!(uf.same(0, 2), true);
            /// ```
            pub fn new(n: usize) -> Self {
                UnionFind {
                    parent_or_size: vec![ParentOrSize::Size(1); n],
                    group_num: n,
                }
            }

            /// Return the representative node of the connected component containing node `a`.
            ///
            /// At that time, perform path compression on the nodes on the path from node `a` to the representative node.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// uf.merge(1, 2);
            /// assert_eq!(uf.leader(0), 0);
            /// assert_eq!(uf.leader(1), uf.leader(2));
            /// ```
            pub fn leader(&mut self, a: usize) -> usize {
                // If node `a` is a representative node of the connected component, return `a`.
                if let ParentOrSize::Size(_) = self.parent_or_size[a] {
                    return a;
                }

                // Path from node `a` to the representative node.
                let mut path = vec![];

                // Current node.
                let mut current = a;

                // Record the path to the representative node.
                while let ParentOrSize::Parent(parent) = self.parent_or_size[current] {
                    // Add current node to the path.
                    path.push(current);

                    // Move to the parent node.
                    current = parent;
                }

                // The representative node of the connected component.
                let leader = current;

                // Set nodes on the path as direct children of the representative node.
                path.iter().for_each(|&node| {
                    self.parent_or_size[node] = ParentOrSize::Parent(leader);
                });

                // Return the representative node of the connected component.
                leader
            }

            /// Return whether two nodes `a` and `b` are in the same connected component.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(0, 1);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(2, 1);
            /// assert_eq!(uf.same(0, 2), true);
            /// ```
            pub fn same(&mut self, a: usize, b: usize) -> bool {
                self.leader(a) == self.leader(b)
            }

            /// Merge each connected component containing nodes `a` and `b`.
            ///
            /// Return `true` if different connected components are newly merged.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(0, 1);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(2, 1);
            /// assert_eq!(uf.same(0, 2), true);
            /// ```
            pub fn merge(&mut self, a: usize, b: usize) -> bool {
                // Representative node of the connected component that contains the node `a`.
                let leader_a = self.leader(a);
                // Representative node of the connected component that contains the node `b`.
                let leader_b = self.leader(b);

                // If nodes `a` and `b` are in the same connected component, return `false` without processing.
                if leader_a == leader_b {
                    return false;
                }

                // Number of nodes of the component containing node `a`.
                let component_size_a = self.size(leader_a);

                // Number of nodes of the component containing node `b`.
                let component_size_b = self.size(leader_b);

                // Number of nodes of the merged component.
                let merged_component_size = component_size_a + component_size_b;

                // Set the parent of the representative node of the smaller sized connected component
                // to be the parent of the other connected component.
                if component_size_a <= component_size_b {
                    self.parent_or_size[leader_a] = ParentOrSize::Parent(leader_b);
                    self.parent_or_size[leader_b] = ParentOrSize::Size(merged_component_size);
                } else {
                    self.parent_or_size[leader_b] = ParentOrSize::Parent(leader_a);
                    self.parent_or_size[leader_a] = ParentOrSize::Size(merged_component_size);
                }

                // Decrease the number of connected components by one.
                self.group_num -= 1;

                // Return `true` because different connected components are newly combined.
                true
            }

            /// Return a list of connected components.
            ///
            /// Each connected component consists of indexes of nodes.
            /// The indexes of the nodes in each connected component are arranged in ascending order.
            /// The list of connected components is sorted in ascending order
            /// with respect to the smallest index of the included nodes.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(5);
            /// uf.merge(1, 2);
            /// uf.merge(2, 3);
            /// assert_eq!(uf.groups(), vec![vec![0], vec![1, 2, 3], vec![4]]);
            /// ```
            pub fn groups(&mut self) -> Vec<Vec<usize>> {
                // Number of nodes in graph.
                let element_num = self.parent_or_size.len();

                // List of connected components.
                let mut groups: Vec<Vec<usize>> = vec![];
                // Correspondence between the representative node and group index.
                let mut leader_to_idx: Vec<Option<usize>> = vec![None; element_num];

                // Assign each node in the graph to a group.
                for node in 0..element_num {
                    // Representative node of the connected component to which the `node` belongs.
                    let leader = self.leader(node);

                    if let Some(group_idx) = leader_to_idx[leader] {
                        // Assign to an existing group.
                        groups[group_idx].push(node);
                    } else {
                        // Adding a new group.
                        leader_to_idx[leader] = Some(groups.len());
                        groups.push(vec![node]);
                    }
                }

                // Return a list of groups.
                groups
            }

            /// Return the number of nodes in the connected component to which node `a` belongs.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// assert_eq!(uf.size(0), 1);
            /// uf.merge(0, 1);
            /// assert_eq!(uf.size(0), 2);
            /// uf.merge(2, 1);
            /// assert_eq!(uf.size(0), 3);
            /// ```
            pub fn size(&mut self, a: usize) -> usize {
                let leader = self.leader(a);

                match self.parent_or_size[leader] {
                    ParentOrSize::Parent(_) => panic!(),
                    ParentOrSize::Size(size) => size,
                }
            }

            /// Add a new node with degree `0`.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(4);
            /// uf.merge(1, 2);
            /// uf.merge(2, 3);
            /// assert_eq!(uf.groups(), vec![vec![0], vec![1, 2, 3]]);
            /// uf.add();
            /// assert_eq!(uf.groups(), vec![vec![0], vec![1, 2, 3], vec![4]]);
            /// ```
            pub fn add(&mut self) {
                self.parent_or_size.push(ParentOrSize::Size(1));
                self.group_num += 1;
            }

            /// Return the number of connected components.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// assert_eq!(uf.group_num(), 3);
            /// uf.merge(0, 1);
            /// assert_eq!(uf.group_num(), 2);
            /// uf.merge(2, 1);
            /// assert_eq!(uf.group_num(), 1);
            /// ```
            pub fn group_num(&self) -> usize {
                self.group_num
            }

            /// Return the number of nodes in the graph.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(5);
            /// assert_eq!(uf.elem_num(), 5);
            /// ```
            pub fn elem_num(&self) -> usize {
                self.parent_or_size.len()
            }
        }
    }

    pub mod scc {
        #[derive(Debug, Clone)]
        pub struct SCC {
            graph: Vec<Vec<usize>>,
            inv_graph: Vec<Vec<usize>>,
        }

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

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

            pub fn scc(&self) -> Vec<Vec<usize>> {
                let n = self.graph.len();

                let mut order = vec![];
                let mut visited = vec![false; n];
                for start_node in 0..n {
                    if !visited[start_node] {
                        order.append(&mut post_order_traversal(
                            &self.graph,
                            &mut visited,
                            start_node,
                        ));
                    }
                }

                let mut scc = vec![];
                let mut visited = vec![false; n];
                for &start_node in order.iter().rev() {
                    if !visited[start_node] {
                        scc.push(post_order_traversal(
                            &self.inv_graph,
                            &mut visited,
                            start_node,
                        ));
                    }
                }

                scc
            }
        }

        fn post_order_traversal(
            graph: &Vec<Vec<usize>>,
            visited: &mut Vec<bool>,
            start_node: usize,
        ) -> Vec<usize> {
            let mut post_order = vec![];

            let mut stack = vec![(start_node, false)];

            while let Some((node, back)) = stack.pop() {
                if back {
                    post_order.push(node);
                }

                if visited[node] {
                    continue;
                }

                visited[node] = true;

                stack.push((node, true));

                stack.extend(graph[node].iter().map(|&next_node| (next_node, false)));
            }

            post_order
        }
    }
}
0