京东笔试题-完全多部图

第二题AC。

思路：对于每个测试用例，我们用一个字典去存储，字典的key是所有的结点，每一个结点的值是一个list，保存的是所有跟key有边相连的结点。字典构造完之后把每个key对应的list进行排序。再之后，我们把有着相同list的值放到一起，这个子集就有可能是最后的子集，同时把这个list也存下来。最后我们得到ret和ret2两个list，ret中的每个元素是ret[i]一个list，这个list中的所有元素在字典中有着相同的value，且ret2即为这个value。最后遍历ret，如果set(range(1, N+1)).difference(ret[i]) != ret2[i]，则可以返回No。遍历到最后如果没有出现不等的情况，则可以打印Yes了。

import sys
T = int(sys.stdin.readline().strip())
examples = []
nums = []
for i in range(T):
    N, M = map(int, sys.stdin.readline().split())
    lines = []
    for j in range(M):
        x, y = map(int, sys.stdin.readline().split())
        lines.append([x, y])
    examples.append(lines)
    nums.append([N, M])
for t in range(T):
    lines = examples[t]
    N, M = nums[t]
    dic = {}
    for i in range(1, N+1):
        dic[i] = []
    for i in range(M):
        x, y = lines[i]
        dic[x].append(y)
        dic[y].append(x)
    for i in dic.keys():
        dic[i].sort()
    ret = []
    ret2 = []
    for i in dic.keys():
        flag = False
        for j in range(len(ret2)):
            if dic[i] == ret2[j]:
                ret[j].append(i)
                flag = True
                break
        if not flag:
            ret.append([i])
            ret2.append(dic[i])
    retflag = True
    n = len(ret)
    for i in range(len(ret)):
        set1 = ret[i]
        set1 = list(set(list(range(1, N+1))).difference(set(set1)))
        set1.sort()
        set2 = ret2[i]
        if set1 != set2:
            retflag = False
            break
    if retflag:
        print('Yes')
    else:
        print('No')