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);
        }
    }
}

结果

 False
True
True
请按任意键继续. . .

简单说下，算法就是根据
连通的无向图有欧拉路径的充要条件是：无向图奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2。
求出每个节点的度数，然后判断度数为奇数的顶点的个数。