99342024-03-18 23:48:5042Fertőzési sorozat (50 pont)python3Elfogadva 50/50141ms14828 KiB
# O(N*(N+M))

from sys import stdin
input=stdin.readline

def solv():
    N,M,K = [int(x) for x in input().split()]
    F = [int(x)-1 for x in input().split()]
    graph=[[] for i in range(N)]
    for i in range(M):
        A,B = [int(x) for x in input().split()]
        graph[A-1].append(B-1)
        graph[B-1].append(A-1)
    #print(graph,N,M,K,F)

    def teszt(v):
        #print('v:',v)
        seen=[0]*N
        seen[v]=1
        cur=[v]
        index=0
        if F[0]==v:
            index=1
        while cur:
            #print('cur:',cur,index)
            tmp=set()
            for v in cur:
                for w in graph[v]:
                    if seen[w]==0:
                        seen[w]=1
                        tmp.add(w)
            oldindex=index
            while index<K and F[index] in tmp:
                index+=1
            #print('tmp:',tmp,oldindex,index)
            if index==K:
                return True
            if index==oldindex and oldindex!=0:
                return False
            if oldindex!=0 and index!=oldindex+len(tmp):
                return False
            cur=tmp
        return False
    
    res=''
    db=0
    for i in range(N):
        if teszt(i):
            db+=1
            res+=str(i+1)+' '
    print(db)
    print(res)
    
solv()
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/017ms11380 KiB
2Elfogadva0/018ms12032 KiB
3Elfogadva0/039ms11924 KiB
4Elfogadva2/217ms12024 KiB
5Elfogadva2/224ms11936 KiB
6Elfogadva2/237ms12392 KiB
7Elfogadva2/235ms12352 KiB
8Elfogadva2/237ms12632 KiB
9Elfogadva2/239ms12976 KiB
10Elfogadva2/2128ms13392 KiB
11Elfogadva1/120ms13364 KiB
12Elfogadva2/264ms13300 KiB
13Elfogadva2/275ms13176 KiB
14Elfogadva2/282ms13476 KiB
15Elfogadva2/246ms13684 KiB
16Elfogadva2/279ms13664 KiB
17Elfogadva2/2108ms13936 KiB
18Elfogadva1/1108ms13916 KiB
19Elfogadva1/163ms13784 KiB
20Elfogadva1/146ms13940 KiB
21Elfogadva1/1120ms14140 KiB
22Elfogadva1/1108ms14588 KiB
23Elfogadva1/1112ms14432 KiB
24Elfogadva1/1123ms14212 KiB
25Elfogadva1/1138ms14028 KiB
26Elfogadva1/1133ms14100 KiB
27Elfogadva1/1136ms13992 KiB
28Elfogadva1/197ms14216 KiB
29Elfogadva1/1114ms14320 KiB
30Elfogadva1/1103ms14336 KiB
31Elfogadva1/1104ms14140 KiB
32Elfogadva1/1136ms14616 KiB
33Elfogadva1/1112ms14428 KiB
34Elfogadva1/1141ms14736 KiB
35Elfogadva1/1112ms14828 KiB
36Elfogadva1/1120ms14820 KiB
37Elfogadva1/1115ms14736 KiB
38Elfogadva1/1108ms14828 KiB
39Elfogadva1/1118ms14796 KiB
40Elfogadva1/1136ms14780 KiB