節點之間-Java C#解決歐拉一筆畫問題

Java C#解決歐拉一筆畫問題

一筆畫問題是圖論中一個著名的問題。一筆畫問題起源於柯尼斯堡七橋問題。數學家歐拉在他1736年發表的論文《柯尼斯堡的七橋》中不僅解決了七橋問題，也提出了一筆畫定理，順帶解決了一筆畫問題。一般認為，歐拉的研究是圖論的開端。

一筆畫問題是柯尼斯堡問題經抽象化後的推廣，是圖遍歷問題的一種。在柯尼斯堡問題中，如果將橋所連接的地區視為點，將每座橋視為一條邊，那麼問題將變成：對於一個有著四個頂點和七條邊的連通圖 ，能否找到一個恰好包含了所有的邊，並且沒有重復的路徑。歐拉將這個問題推廣為：對於一個給定的連通圖，怎樣判斷是否存在著一個恰好包含了所有的邊，並且沒有重復的路徑？這就是一筆畫問題。用圖論的術語來說，就是判斷這個圖是否是一個能夠遍歷完所有的邊而沒有重復。這樣的圖現稱為歐拉圖。這時遍歷的路徑稱作歐拉路徑，如果路徑閉合，則稱為歐拉回路。一筆畫問題的推廣是多筆畫問題，即對於不能一筆畫的圖，探討最少能用多少筆來畫成。

對於一筆畫問題，有兩個判斷的准則，它們都由歐拉提出並證明。
定理一
連通的無向圖有歐拉路徑的充要條件是：無向圖奇頂點（連接的邊數量為奇數的頂點）的數目等於0或者2。
連通的無向圖是歐拉環（存在歐拉回路）的充要條件是：每個頂點的度都是偶數。

定理二
如果連通無向圖 有 個奇頂點，那麼它可以用 筆畫成，並且至少要用 筆畫成。

輸入一些二元組，二元組代表兩個節點之間擁有一條通路，比如(a,b)表示a可以到達b，b也可以到達a。然後給出判斷此圖是否可以一筆畫。

輸入示范
3
a,b
a,c
b,c
輸出示范
true

最佳回答：

寫一個給你

 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string input1 = @"a,b
b,c
b,d
d,e
d,f"; // 工字形
            string input2 = @"a,b
b,c
c,a"; // 三角形
            string input3 = @"a,b
a,c
b,d
c,d
c,e
d,f
e,f"; // 液晶8字形
            Console.WriteLine(Solve(input1));
            Console.WriteLine(Solve(input2));
            Console.WriteLine(Solve(input3));
        }

        static bool Solve(string input)
        {
            var query = input.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries)
                .Select(x => x.Split(',')[0] + x.Split(',')[1]);
            var query1 = string.Concat(query).Distinct().Select(x => query.Count(y => y.Contains(x)));
            int query2 = query1.Count(x => x % 2 == 1);
            return (query2 == 0 || query2 == 2);
        }
    }
}