196682025-12-18 11:35:53birozsHálózati biztonság (50)python3Időlimit túllépés 24/50400ms29996 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 azokat a csúcsokat, melynek legalább K szomszédja van
T = []
for k,L in G.items():
    if len(L) >= K:
        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
base24/50
1Elfogadva0/016ms3260 KiB
2Időlimit túllépés0/0319ms18988 KiB
3Elfogadva2/216ms3124 KiB
4Elfogadva2/217ms3124 KiB
5Hibás válasz0/217ms3124 KiB
6Elfogadva2/216ms3124 KiB
7Elfogadva2/217ms3312 KiB
8Időlimit túllépés0/2400ms3172 KiB
9Elfogadva2/216ms3316 KiB
10Időlimit túllépés0/2400ms3956 KiB
11Elfogadva2/286ms3640 KiB
12Időlimit túllépés0/2379ms4132 KiB
13Elfogadva3/320ms3732 KiB
14Elfogadva3/337ms5016 KiB
15Elfogadva3/376ms6516 KiB
16Időlimit túllépés0/3356ms16176 KiB
17Elfogadva3/339ms4848 KiB
18Időlimit túllépés0/3384ms11564 KiB
19Időlimit túllépés0/3377ms26848 KiB
20Időlimit túllépés0/3389ms29996 KiB
21Időlimit túllépés0/3391ms27944 KiB
22Időlimit túllépés0/3382ms3124 KiB