196662025-12-18 11:20:37birozsHálózati biztonság (50)python3Time limit exceeded 24/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)




SubtaskSumTestVerdictTimeMemory
base24/50
1Accepted0/016ms3148 KiB
2Time limit exceeded0/0381ms24364 KiB
3Accepted2/216ms3244 KiB
4Accepted2/217ms3112 KiB
5Wrong answer0/216ms3068 KiB
6Accepted2/216ms3136 KiB
7Accepted2/217ms3208 KiB
8Time limit exceeded0/2379ms3276 KiB
9Accepted2/217ms3120 KiB
10Time limit exceeded0/2381ms4000 KiB
11Accepted2/287ms3768 KiB
12Time limit exceeded0/2386ms4428 KiB
13Accepted3/323ms3884 KiB
14Accepted3/345ms5720 KiB
15Accepted3/383ms8384 KiB
16Time limit exceeded0/3402ms19248 KiB
17Accepted3/343ms5272 KiB
18Time limit exceeded0/3379ms16168 KiB
19Time limit exceeded0/3349ms32000 KiB
20Time limit exceeded0/3402ms30512 KiB
21Time limit exceeded0/3372ms32000 KiB
22Time limit exceeded0/3379ms3124 KiB