# Struct ac_library::dsu::Dsu

pub struct Dsu { /* private fields */ }
Expand description

A Disjoint set union (DSU) with union by size and path compression.

In the following documentation, let $n$ be the size of the DSU.

## Example

use ac_library::Dsu;
use proconio::{input, source::once::OnceSource};

input! {
from OnceSource::from(
"5\n\
3\n\
0 1\n\
2 3\n\
3 4\n",
),
n: usize,
abs: [(usize, usize)],
}

let mut dsu = Dsu::new(n);
for (a, b) in abs {
dsu.merge(a, b);
}

assert!(dsu.same(0, 1));
assert!(!dsu.same(1, 2));
assert!(dsu.same(2, 4));

assert_eq!(
dsu.groups()
.into_iter()
.map(|mut group| {
group.sort_unstable();
group
})
.collect::<Vec<_>>(),
[&[0, 1][..], &[2, 3, 4][..]],
);

## Implementations§

source§

### impl Dsu

source

#### pub fn new(size: usize) -> Self

Creates a new Dsu.

##### Constraints
• $0 \leq n \leq 10^8$
##### Complexity
• $O(n)$
source

#### pub fn merge(&mut self, a: usize, b: usize) -> usize

Performs the Uɴɪᴏɴ operation.

##### Constraints
• $0 \leq a < n$
• $0 \leq b < n$
##### Panics

Panics if the above constraints are not satisfied.

##### Complexity
• $O(\alpha(n))$ amortized
source

#### pub fn same(&mut self, a: usize, b: usize) -> bool

Returns whether the vertices $a$ and $b$ are in the same connected component.

##### Constraints
• $0 \leq a < n$
• $0 \leq b < n$
##### Panics

Panics if the above constraint is not satisfied.

##### Complexity
• $O(\alpha(n))$ amortized
source

#### pub fn leader(&mut self, a: usize) -> usize

Performs the Fɪɴᴅ operation.

##### Constraints
• $0 \leq a < n$
##### Panics

Panics if the above constraint is not satisfied.

##### Complexity
• $O(\alpha(n))$ amortized
source

#### pub fn size(&mut self, a: usize) -> usize

Returns the size of the connected component that contains the vertex $a$.

##### Constraints
• $0 \leq a < n$
##### Panics

Panics if the above constraint is not satisfied.

##### Complexity
• $O(\alpha(n))$ amortized
source

#### pub fn groups(&mut self) -> Vec<Vec<usize>>

Divides the graph into connected components.

The result may not be ordered.

##### Complexity
• $O(n)$

§

§

§

§

§

## Blanket Implementations§

source§

### impl<T> Any for Twhere T: 'static + ?Sized,

source§

#### fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

### impl<T> Borrow<T> for Twhere T: ?Sized,

const: unstable · source§

#### fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

### impl<T> BorrowMut<T> for Twhere T: ?Sized,

const: unstable · source§

#### fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

### impl<T> From<T> for T

const: unstable · source§

#### fn from(t: T) -> T

Returns the argument unchanged.

source§

### impl<T, U> Into<U> for Twhere U: From<T>,

const: unstable · source§

#### fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

### impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

#### type Error = Infallible

The type returned in the event of a conversion error.
const: unstable · source§

#### fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

### impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

#### type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
const: unstable · source§

#### fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.