KY34 Is It A Tree?

KY34 Is It A Tree?

import sys

def main(info, CaseNum):  # info是一个字符串
    if info.strip() == '':
        print('Case {0} is a tree.'.format(CaseNum))
        return
    lsInfo = list()
    info = info.strip().split()
    length = len(info)
    if length % 2 == 1:
        print('输入的节点数量不是偶数!!!')
        return
    for i in range(0,length-1,2):
        lsInfo.append(info[i]+' '+info[i+1])
    # print("Case"+str(CaseNum),lsInfo)
    # return
    # EdgeSet存储边集合;InEdgeDict存储节点的入边;OutEdgeDict存储节点的出边
    VertexSet, EdgeList, InEdgeDict, OutEdgeDict = set(), list(), dict(), dict()
    for item in lsInfo:
        src, dst = map(int, item.split())  # src --> dst
        VertexSet.update({src,dst})
        if src == dst: # 表示存在自回路
            print('Case {0} is not a tree.'.format(CaseNum))
            return
        EdgeList.append((src, dst))
        if src in OutEdgeDict:  # src --> dst
            OutEdgeDict[src].append(dst)
        else:
            OutEdgeDict[src] = [dst]
        if dst in InEdgeDict:
            InEdgeDict[dst].append(src)
        else:
            InEdgeDict[dst] = [src]
    #######################################
    # 检查|V|-1==|E|
    if len(VertexSet) - 1 != len(EdgeList):
        print('Case {0} is not a tree.'.format(CaseNum))
        return
    # 寻找根节点,计算入度1和入度0的节点,并检查根节点的出度不为0
    root, rootNum = -1, 0
    for vertex in VertexSet:
        InEdges = InEdgeDict.get(vertex,list())
        if len(InEdges) > 1:
            print('Case {0} is not a tree.'.format(CaseNum))
            return
        elif len(InEdges) == 0:
            root, rootNum = vertex, rootNum + 1
    if rootNum != 1:
        print('Case {0} is not a tree.'.format(CaseNum))
        return
    elif len(OutEdgeDict.get(root,list())) < 1:
        print('Case {0} is not a tree.'.format(CaseNum))
        return
    else:
        print('Case {0} is a tree.'.format(CaseNum))

if __name__ == '__main__':
    infoList = list()
    for line in sys.stdin:
        line = line.strip()
        if line == '':
            continue
        line = list(map(str, line.split()))
        for s in line:
            if int(s) > 0:
                infoList.append(s)
            elif int(s) == 0:
                infoList.append("#")
    info = ' '.join(infoList)  
    infoList = info[0:-4].split('# #')  
    CaseNum = 0
    for info in infoList:
        CaseNum += 1
        main(info, CaseNum)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74