99332024-03-18 23:28:2842Fertőzési sorozat (50 pont)python3Hibás válasz 42/50143ms14992 KiB
# O(?)

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
            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
base42/50
1Elfogadva0/017ms11340 KiB
2Elfogadva0/017ms11732 KiB
3Elfogadva0/039ms12224 KiB
4Elfogadva2/217ms11960 KiB
5Elfogadva2/224ms12444 KiB
6Elfogadva2/237ms12484 KiB
7Elfogadva2/235ms12840 KiB
8Elfogadva2/237ms12784 KiB
9Elfogadva2/237ms12820 KiB
10Elfogadva2/2128ms12844 KiB
11Elfogadva1/119ms12644 KiB
12Elfogadva2/264ms12856 KiB
13Elfogadva2/275ms12768 KiB
14Elfogadva2/281ms12928 KiB
15Elfogadva2/246ms12884 KiB
16Elfogadva2/278ms12824 KiB
17Elfogadva2/2108ms13076 KiB
18Elfogadva1/1108ms12892 KiB
19Elfogadva1/163ms12992 KiB
20Elfogadva1/146ms13192 KiB
21Elfogadva1/1128ms13284 KiB
22Elfogadva1/1115ms13384 KiB
23Elfogadva1/1118ms13820 KiB
24Hibás válasz0/1126ms13780 KiB
25Elfogadva1/1142ms14052 KiB
26Elfogadva1/1136ms14328 KiB
27Hibás válasz0/1140ms14408 KiB
28Hibás válasz0/1103ms14396 KiB
29Elfogadva1/1119ms14380 KiB
30Hibás válasz0/1104ms14872 KiB
31Hibás válasz0/1109ms14992 KiB
32Elfogadva1/1137ms14836 KiB
33Elfogadva1/1125ms14780 KiB
34Hibás válasz0/1141ms14924 KiB
35Hibás válasz0/1114ms14772 KiB
36Hibás válasz0/1128ms14600 KiB
37Elfogadva1/1126ms14492 KiB
38Elfogadva1/1115ms14680 KiB
39Elfogadva1/1118ms14504 KiB
40Elfogadva1/1143ms14692 KiB