No.2910 Introduction to Simplicial Homology
Problem Statement
You are given as input a positive integer $N$, a non-negative integer $M$, an undirected graph $G$ with $N$ vertices and $M$ edges (without self-loops or multiple edges) whose vertices are the non-negative integers less than $N$, and $3$ non-negative integers $v_0, v_1, v_2$ less than $N$.
Determine whether there exists a cycle of $G$ such that the set of all vertices it passes through does not coincide with $\{v_0, v_1, v_2\}$.
Here, a cycle of $G$ is, roughly speaking, a path moving between vertices along edges of $G$ whose start and end are the same and which otherwise passes through pairwise distinct vertices.
An explanation for those who want the rigorous definition of a cycle is here. (Click to open)
A cycle of $G$ is a finite sequence $e$ of edges of $G$ of length at least $1$ such that, denoting its length by $\ell$ and, for each non-negative integer $j$ less than $\ell$, denoting the $1+j$-th component of $e$ by $e_j$, the following $2$ conditions are satisfied:
- For any integers $j_0,j_1$ satisfying $0 \leq j_0 < j_1 < \ell$, we have $e_{j_0} \neq e_{j_1}$.
- There exists a sequence $c$ of vertices of $G$ of length $\ell + 1$ such that, denoting the $1+i$-th component of $c$ by $c_i$ for each non-negative integer $i$ less than or equal to $\ell$, the following $2$ conditions are satisfied:
- For any integer $j$ satisfying $0 \leq j < \ell$, $e_j$ is an edge of $G$ connecting $c_j$ and $c_{j+1}$.
- For any integers $i_0,i_1$ satisfying $0 \leq i_0 < i_1 \leq \ell$, $(i_0,i_1) = (0,\ell)$ and $c_{i_0} = c_{i_1}$ are equivalent.
Also, in the above notation, a vertex that $e$ passes through is a vertex $v$ of $G$ for which there exists a non-negative integer $j$ less than $\ell$ such that $v$ is an endpoint of $e_j$.
Background
For geometric data called simplicial complexes, a graded invariant called simplicial homology is defined. Simplicial homology is data in which an algebraic structure called an abelian group, among other things, is assigned to each degree, and for each non-negative integer $d$, the data of degree $d$ is called the degree $d$ simplicial homology group.
This problem is closely related to the problem of determining whether the $2$-dimensional simplicial complex, obtained by attaching a face corresponding to $\{v_0,v_1,v_2\}$ to the $1$-dimensional simplicial complex constructed from $G$, has the property that its degree $1$ simplicial homology group is the trivial group. However, while the problem of computing the degree $1$ simplicial homology group requires that the edges corresponding to the subsets $\{v_0,v_1\}, \{v_0,v_2\}, \{v_1,v_2\}$ of $\{v_0,v_1,v_2\}$ all be edges of $G$, this problem itself does not need such a constraint, so it is not imposed.
Input
The edges of $G$ are numbered by the non-negative integers $m$ less than $M$ and called edge $m$. For each non-negative integer $m$ less than $M$, let $i_m$ and $j_m$ ($i_m,j_m$ are non-negative integers less than $N$ satisfying $i_m < j_m$) be the endpoints of edge $m$.
Then, the input is given from standard input in $2 + M$ lines in the following format:
- Line $1$ contains $N, M$ separated by a half-width space.
- For each non-negative integer $m$ less than $M$, line $2 + m$ contains $i_m, j_m$ separated by a half-width space.
- Line $2 + M$ contains $v_0, v_1, v_2$ separated by half-width spaces.
$N$ $M$
$i_0$ $j_0$
$\vdots$
$i_{M-1}$ $j_{M-1}$
$v_0$ $v_1$ $v_2$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 4$.
- $M$ is an integer satisfying $0 \leq M \leq \frac{1}{2}N(N-1)$.
- For any non-negative integer $m$ less than $M$, $i_m$ and $j_m$ are integers satisfying $0 \leq i_m < j_m < N$.
- For any non-negative integers $m_0,m_1$ less than $M$, if $m_0 \neq m_1$ then $(i_{m_0},j_{m_0}) \neq (i_{m_1},j_{m_1})$.
- $v_0$ is an integer satisfying $0 \leq v_0 < N$.
- $v_1$ is an integer satisfying $0 \leq v_1 < N$.
- $v_2$ is an integer satisfying $0 \leq v_2 < N$.
Output
Print Yes if there exists a cycle of $G$ such that the set of all vertices it passes through does not coincide with $\{v_0, v_1, v_2\}$, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
3 3 0 1 0 2 1 2 0 0 0
As shown here, $v_0, v_1, v_2$ may contain duplicates.
Output
Yes
The path traversing "edge $0$, edge $2$, edge $1$" forms a cycle, and the set of all vertices it passes through is $\{0,1,2\}$, which does not coincide with $\{v_0,v_1,v_2\} = \{0,0,0\} = \{0\}$.
Sample 2
Input
3 3 0 1 0 2 1 2 2 0 1
As shown here, $v_0, v_1, v_2$ may not be in ascending order.
Output
No
The path traversing "edge $0$, edge $2$, edge $1$" forms a cycle, but the set of all vertices it passes through, $\{0,1,2\}$, coincides with $\{v_0,v_1,v_2\} = \{2,0,1\}$. The same applies to the other cycles.
Sample 3
Input
4 4 0 1 0 3 1 2 2 3 0 1 2
As shown here, $G$ may not have the edges corresponding to the subsets $\{v_0,v_1\}, \{v_0,v_2\}, \{v_1,v_2\}$ of $\{v_0, v_1, v_2\}$. In this case, $G$ has no edge corresponding to $\{v_0,v_2\} = \{0,2\}$.
Output
Yes
The path traversing "edge $0$, edge $2$, edge $3$, edge $1$" forms a cycle, and the set of all vertices it passes through is $\{0,1,2,3\}$, which does not coincide with $\{v_0,v_1,v_2\} = \{0,1,2\}$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。