196692025-12-18 11:38:18birozsHálózati biztonság (50)python3Time limit exceeded 24/50400ms28456 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(len(T)):
    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)




SubtaskSumTestVerdictTimeMemory
base24/50
1Accepted0/016ms3120 KiB
2Time limit exceeded0/0317ms18992 KiB
3Accepted2/217ms3224 KiB
4Accepted2/217ms3124 KiB
5Wrong answer0/217ms3124 KiB
6Accepted2/217ms3308 KiB
7Accepted2/218ms3124 KiB
8Time limit exceeded0/2400ms3120 KiB
9Accepted2/217ms3268 KiB
10Time limit exceeded0/2400ms4016 KiB
11Accepted2/289ms3636 KiB
12Time limit exceeded0/2386ms4132 KiB
13Accepted3/320ms3736 KiB
14Accepted3/339ms5016 KiB
15Accepted3/375ms6364 KiB
16Time limit exceeded0/3386ms16048 KiB
17Accepted3/337ms4852 KiB
18Time limit exceeded0/3386ms11428 KiB
19Time limit exceeded0/3344ms27004 KiB
20Time limit exceeded0/3389ms28456 KiB
21Time limit exceeded0/3386ms28032 KiB
22Time limit exceeded0/3400ms3032 KiB