[UVA] 11393 - Tri-Isomorphism
|
I I U C O N L I N E C O N T E S T 2 0 0 8 |
|
|
Problem I: Tri-Isomorphism |
|
|
Input: standard input Output: standard output |
|
|
|
|
|
Let V(G) be the vertex set of a simple graph & E(G) its edge set. An Isomorphism from a simple graph G to a simple graph H is a bijection f: V(G)→V(H) such that uv є E(G) if & only if f(u)f(v) є E(H). We say, G is isomorphic to H if there is an isomorphism from G to H.
A complete graph is a simple graph whose vertices are pairwise adjacent: the unlabeled complete graph with n vertices is denoted Kn. For example, the following figure shows K5.
Finally, a decomposition of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list.
Now, given a positive integer n, you are to determine if Kn decomposes into three pairwise-isomorphic subgraphs.
|
|
|
Input |
|
|
First line of each test case consists of a positive integer n (n<=100). The end of input will be indicated by a case where n=0. This case should not be processed.
|
|
|
Output |
|
|
For each test case, print YES if Kn can be decomposed into three pairwise-isomorphic subgraphs & NO otherwise.
|
|
|
Constraints |
|
|
- n < 100
|
|
|
Sample Input |
Output for Sample Input |
|
4 5 0 |
YES NO |
|
|
|
|
Problem setter: Mohammad Mahmudur Rahman |
|
把一張完全圖(即兩兩節點間都有邊)的圖形，每個邊只使用一次，拆成 3 個 sub-graph，並且兩兩同構，同構跟化合物一樣的方式，看形狀的同構。
由於拆成 3 個子圖，也就是說原本的邊也要是 3 的倍數，這個必要條件。
但還不曉得是否為充分必要條件，那麼就直接上了。AC
#include <stdio.h>
int main() {
int n;
while(scanf("%d", &n) == 1 && n) {
puts(n >= 3 && (n%3 == 0 || (n-1)%3 == 0) ? "YES" : "NO");
}
return 0;
}