''' 这个题 n个人 m个团队 每个人的编号是一定的,0-n-1 ''' class Solution(): def allPerson(self, personNum, setNum, SETLIST): #personNum: #setNum: #SETLIST: all set AllSet = [] perDict = {}#from person to list (set num) for i in range(setNum): theset = SETLIST[i] #from set to person AllSet.append(theset) #build the dict for all person #从person to set for person in theset: if person not in perDict: perDict[person]=[i] else: perDict[person].append(i) found = [0]*personNum def dfs(person, found): if found[person] == 0:#not fouund found[person]=1 if person not in perDict: return for theset in perDict[person]: #遍历这个theset for setPerson in AllSet[theset]: if found[setPerson]==0: dfs(setPerson, found) if 0 in perDict: dfs(0, found) return sum(found) def test(): case=Solution() ans = case.allPerson(5,2,[[1,2,0], [4,1]]) print(ans) # test() def inputFun(): personNum, setNum = map(int, input().strip().split()) AllList = [] for i in range(setNum): li = list(map(int, input().strip().split())) if li[0]==0: AllList.append([]) continue AllList.append(li[1:]) return personNum, setNum, AllList def main(): personNum, SetNum, AllList = inputFun() case = Solution() ans = case.allPerson(personNum, SetNum, AllList) print(ans) main()
全部评论
(0) 回帖