b924: kevin 愛畫畫

2019-08-21

內容

kevin 很喜歡畫畫但是 kevin 畫圖有個原則就是他只用一筆畫把圖畫完

幾天前 kevin 喜歡的女生送了 kevin 一張圖

這張圖上有一些點點之間還有一些邊

他很想幫這張圖上色

但又必須堅守一筆畫的原則

請你告訴 kevin

他能不能用一筆畫畫完這張圖 (( 經過所有的邊

而且每條邊只能經過一次

輸入

第一行有兩個數字 n , m

代表圖上有 n 個點 m 條邊

接下來有 m 行

每行有兩個數字 a b

代表 a b 兩點互相連接

(( n < 10000 , m < 10^7 , 1 <= a , b <= n

((a b 間可能存在不只一條邊

((保證圖為連通圖

4 5
1 2
2 4
3 4
3 1
1 4

4 6
1 2
2 4
3 4
3 1
1 4
2 3

輸出

如果可以一筆畫完成輸出”YES”

否則輸出”NO”

YES

NO

解題思路

用基數排序統計好該點被線段經過的次數，之後結算時如果除 2 不餘 0 代表這個點必須是投或尾，如果這種點超過 3 個，表示 Kevin 無法一筆畫畫完，因為一筆畫只有一個頭和一個尾。

完整程式碼

AC (1.2s, 112KB)

#include <stdio.h>
#include <memory.h>

int list[10000];

int main()
{
    int n, m, f, t, count;
    while (scanf(" %d %d", &n, &m) == 2)
    {
        memset(list + 1, 0, sizeof(int) * n);
        for (int i = 0; i < m; i++)
        {
            scanf(" %d %d", &f, &t);
            list[f]++, list[t]++;
        }
        count = 0;
        for (int i = 1; i <= n; i++)
        {
            if (list[i] & 1)
            {
                count++;
                if (count > 2)
                    break;
            }
        }
        puts(count < 3 ? "YES" : "NO");
    }
    return 0;
}