196672025-12-18 11:21:19birozsHálózati biztonság (50)pypy3Futási hiba 26/50402ms32000 KiB
N,M,K = map(int,input().split())
#A legtöbb szomszéddal rendelkező csúcstól kezdve meghatározzuk a kölcsönös szomszédok halmazás
#Szomszédsági listák előállítása
G = {}
for i in range(1,N+1):
    G[i] = []
for _ in range(M):
    A,B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)
#Szomszédok száma szerint csökkenően rendezzük a csúcsokat
T = []
for k,L in G.items():
    T.append([k,len(L)])
T.sort(key=lambda x:-x[1])
S = []
#Csúcsonként meghatározzuk a részgráfokat
for i in range(N):
    if len(S) > T[i][1]:
        break
    else:
        #R az i csúcs szomszédlistája
        R = G[T[i][0]][:]
        #Megszámoljuk az R-ben lévő csúcsok hány szomszéddal rendelkeznek R-ben
        Db = []
        for k in R:
            x = 0
            for z in G[k]:
                if z in R:
                    x += 1
            Db.append(x)
        # Megnézzük van-e kevés szomszéddal rendelkező csúcs, az ő szomszédai értékét csökkentjük 1-el
        Talal = True
        while Talal:
            Talal = False
            for j in range(len(Db)):
                if Db[j] != 0 and Db[j] < K - 1:
                    Talal = True
                    Db[j] = 0
                    for k in range(len(R)):
                        if R[j] in G[R[k]]:
                            Db[k] -= 1
        #A legalább K-1 szomszéddal rendelkező megmaradt csúcsokat tesszük S-be, ha az nagyobb elemszámú lesz így, mint az eddigi
        x = 0
        for k in Db:
            if k != 0:
                x += 1
        if x > len(S):
            S = [T[i][0]]
            for k in range(len(Db)):
                if Db[k] != 0:
                    S.append(R[k])
print(len(S))
S.sort()
print(*S)




RészfeladatÖsszpontTesztVerdiktIdőMemória
base26/50
1Elfogadva0/043ms19612 KiB
2Futási hiba0/0201ms32000 KiB
3Elfogadva2/248ms21424 KiB
4Elfogadva2/250ms21108 KiB
5Hibás válasz0/259ms21220 KiB
6Elfogadva2/243ms19948 KiB
7Elfogadva2/248ms21480 KiB
8Időlimit túllépés0/2379ms22248 KiB
9Elfogadva2/248ms21212 KiB
10Időlimit túllépés0/2402ms22504 KiB
11Elfogadva2/2100ms23616 KiB
12Elfogadva2/2217ms24364 KiB
13Elfogadva3/364ms22504 KiB
14Elfogadva3/3103ms25064 KiB
15Elfogadva3/3135ms27112 KiB
16Futási hiba0/3194ms32000 KiB
17Elfogadva3/3109ms24516 KiB
18Futási hiba0/3136ms32000 KiB
19Futási hiba0/367ms32000 KiB
20Futási hiba0/368ms32000 KiB
21Futási hiba0/367ms32000 KiB
22Időlimit túllépés0/3402ms21672 KiB