赛码搭积木 Python 非AC100%

题目：

搭积木
时间限制： 5000MS
内存限制： 589824KB

题目描述：

一天，小明买了许多积木回家，他想把这些积木拼接在一起。每块积木有两个接口，每个接口我们用一个数字标记，规定只有当两块积木有相同数字标记的接口时，这两块积木才可以通过该接口拼接在一起。举例，有两块积木，接口数字分别为1，2和3，4，那么这两块积木无法拼接；若两块积木接口数字分别为1，2和2，3，那么这两块积木可以通过由数字2标记的接口拼接在一起。

现在小明知道所有积木的数量和每块积木接口的数字标记，你能告诉他他可以将所有积木拼接成一个整体么？

输入描述

第一行一个整数t，表示测试数组组数1≤t≤10；

接下来在每组测试数据中：

第一行一个整数n，表示积木的数量1≤n≤100000，

下面n行每行2个整数x，y，表示其中一块积木的两个接口的数字标记；1≤x，y≤100000；

输出描述

对于每组测试数据，输出”YES”，表示该组数据中的所有积木可以拼接成一个整体，”NO”表示不行。（注意输出不包括引号）

解法一：查表 AC 36%

t = int(input())
n = []
l = []
for i in range(t):
    n.append(int(input()))
    cur = []
    for i in range(n[-1]):
        cur.append(list(map(int,input().split(' '))))
    l.append(cur)
cur = []
for i in range(t):
    box = l[i]
    box.sort(key=lambda x:(-x[0],-x[1]))
    while len(box)>1:
        if box[-1][0] == box[-2][0]:
            res = [box[-1][1],box[-2][1]]
        elif box[-1][1] == box[-2][0]:
            res = [box[-1][0],box[-2][1]]
        elif box[-1][0] == box[-2][1]:
            res = [box[-1][1],box[-2][0]]
        elif box[-1][1] == box[-2][1]:
            res = [box[-1][0],box[-2][0]]
        else:
            break
        box.pop(-1)
        box.pop(-1)
        box.append(res)
    if len(box) <= 1:
        cur.append('YES')
    else:
        cur.append('NO')
for x in cur:
    print(x)

解法二：欧拉通路 AC 73%

t = int(input())
n = []
l = []
for i in range(t):
    n.append(int(input()))
    cur = []
    for i in range(n[-1]):
        cur.append(list(map(int,input().split(' '))))
    l.append(cur)
cur = []
for i in range(t):
    box = sum(l[i],[])
    d = dict()
    for x in box:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    res = 0
    for x in d:
        if d[x] % 2 != 0:
            res += 1
    if res == 2&nbs***bsp;res == 0:
        cur.append('YES')
    else:
        cur.append('NO')
for x in cur:
    print(x)

解法三：欧拉2 AC 73%

t = int(input())
n = []
l = []
for i in range(t):
    n.append(int(input()))
    cur = []
    for i in range(n[-1]):
        cur.append(list(map(int,input().split(' '))))
    l.append(cur)
cur = []
for i in range(t):
    box = sum(l[i],[])
    d = []
    for x in box:
        if x not in d:
            d.append(x)
        else:
            d.pop(d.index(x))
    if len(d) == 2&nbs***bsp;len(d) == 0:
        cur.append('YES')
    else:
        cur.append('NO')
for x in cur:
    print(x)

#赛码#