投資錢景>買台積電就對了6檔好股票放一年賺5成吉隆坡最便宜行程一覽表不捨學生找「槌」 高中...
2013-08-11 15:31:23 人氣(100) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 11393 - Tri-Isomorphism

0
收藏
0
推薦

 

I I U  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 K­n. 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;
}

11393Tri-Isomorphism
台長:Morris
人氣(100) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA] 10964 - Strange Planet
此分類上一篇:[UVA] 11298 - Dissecting a Hexagon

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文