本节书摘来自异步社区《趣题学算法》一书中的第1章1.4节图的性质，作者徐子珊,更多章节内容可以访问云栖社区“异步社区”公众号查看。
1.4 图的性质
有的计数问题所涉及的事物间存在着某种关系，这样的问题往往可以表示成一个图（Graph）：问题中的每个事物视为一个顶点，两个顶点之间如果存在这关系，就在这两个顶点之间做一条称为边的弧。形式化描述为由问题中的各事物构成的集合，记为顶点集V={v1,v2,…,vn}，边集E={(vi, vj)| vi, vj ∈V且vi和vj具有关系}。
例如，图1-3将五个人Adward、John、Philips、Robin和Smith之间的朋友关系表示成了一个图。其中，Adward与Robin和Smith是朋友，John与Philips和Robin是朋友，Philips与John、Robin和Smith是朋友，Smith与Adward、Philips和Robin是朋友，Robin与其他所有人都是朋友。
图G记为。数学家们对图的研究已经有了百年的历史，有很多很好用的性质能帮助我们轻松地解决计数问题。例如，图论中有一个著名的“握手”定理。
定义1-1
设G=为一无向图，vV，称v作为边的端点次数之和为v的度数，简称为度，记为d(v)。
对图中所有顶点的度数有如下所述的结论。
定理1-1（握手定理）
设G=为任意无向图，V={v1,v2,…,vn}，|E|=m，则
sumnolimits_{i=1}^{n}{d({{v}_{i}})=2m}
即所有顶点的度数之和为边数的2倍。
证 G中每条边（包括环）均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。
握手定理说明，图中各顶点的度数之和必为偶数。
问题描述
百度之星总决赛既是一群编程大牛一决高下的赛场，也是圈内众多网友难得的联欢，在为期一周的聚会中，总少不了各种有趣的游戏。
某年的总决赛聚会中，一个有趣的游戏是这样的：
游戏由Robin主持，一共有N个人参加（包括主持人），Robin让每个人说出自己在现场认识的人数（如果A认识B，则默认B也认识A），在收到所有选手报出的数据后，他来判断是否有人说谎。Robin说，如果他能判断正确，希望每位选手都能在毕业后来百度工作。
为了帮Robin留住这些天才，现在请您帮他出出主意吧。
特别说明：
1．每个人都认识Robin。
2．认识的人中不包括自己。
输入
输入数据包含多组测试用例，每组测试用例有2行，首先一行是一个整数N (1
N为0的时候结束输入。
输出
请根据每组输入数据，帮助主持人Robin进行判断：如果确定有人说谎，请输出“Lie absolutely”；否则，请输出“Maybe truth”。
每组数据的输出占一行。
输入样例
7
5 4 2 3 2 5
7
3 4 2 2 2 3
0
输出样例
Lie absolutely
Maybe truth
解题思路
（1）数据的输入与输出
根据题面中对输入文件格式的描述，文件中有若干个测试案例，每个案例的数据以表示人数的整数N开头，然后有N-1个整数表示除主持人以外的每个人所报告的相识人数。对案例判断其中是否有人说谎，根据计算结果输出一行“Maybe truth”（无人说谎）或“Lie absolutely”（有人说谎）。N=0是输入结束的标志。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取人数N
4 while N≠0
5 do 创建数组a[1..N]
6 for i←1 to N-1
7 do 从inputdata中读取a[i]
8 a[N] ←N-1 ▷Robin认识每个人
9 result← PARTY-GAME(a)
10 if result=true
11 then 将"Maybe truth"作为一行写入outputdata
12 else将"Lie absolutely"作为一行写入outputdata
13 从inputdata中读取案例数据N
14 关闭inputdata
15 关闭outpudata
其中，第9行调用过程PARTY-GAME(a)判断N个人中是否有人说谎，是解决一个案例的关键。
（2）处理一个案例的算法过程
在一个案例中，把两个人相互认识看成一种关系，n个人之间的认识关系将可表示成一个无向图G=。其中，顶点集V={v1,v2,…,vn}表示这n个人，边集E中元素表示两个人之间的认识关系。
利用握手定理，我们将问题中的每一个案例的所有人所报的认识的人数（包括主持人报的n−1）相加，考察和数的奇偶性，若为奇数，则肯定有人撒谎。等价地，设置一个计数器count（初始为0），检测每个人（包括主持人）所报的认识的人数，若是奇数则count增加1，根据count的奇偶性进行判断。伪代码过程表示为如下：
PARTY-GAME(a)
1 n←length[a]
2 count←0
3 for i←1 to n ▷检测每一个人报告的认识人数
4 do if a[i] is odd
5 then count←count+1
6 return count is even
算法1-11 利用握手定理判断晚会中是否有客人说谎的过程
对一个案例而言，假定包括主持人在内，晚会上有n个人，则第3～5行的for循环将重复n次。所以算法对一个案例的运行时间是Θ(n)。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Party Game中，读者可打开文件partygame.cpp研读，并试运行之。
