結果
| 問題 |
No.1605 Matrix Shape
|
| コンテスト | |
| ユーザー |
 atcoder8
|
| 提出日時 | 2023-04-16 14:52:22 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 129 ms / 2,000 ms |
| コード長 | 17,516 bytes |
| コンパイル時間 | 13,204 ms |
| コンパイル使用メモリ | 399,976 KB |
| 実行使用メモリ | 23,772 KB |
| 最終ジャッジ日時 | 2024-10-11 23:46:31 |
| 合計ジャッジ時間 | 16,725 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
ソースコード
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
}
}
}