148772025-02-05 21:46:32feheristvanHálózati biztonság (50)python3Futási hiba 38/50209ms32000 KiB
import sys
from collections import deque

def find_max_k_secure_subnetwork(n, m, k, edges):
    # Szomszédsági lista létrehozása
    adj = [set() for _ in range(n + 1)]
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    
    # Kezdetben minden csúcs aktív
    active_nodes = set(range(1, n + 1))
    degree = [len(adj[i]) for i in range(n + 1)]
    
    # Sor a törlendő csúcsokhoz
    queue = deque()
    for i in range(1, n + 1):
        if degree[i] < k:
            queue.append(i)
    
    # Iteratív csökkentés
    while queue:
        node = queue.popleft()
        if node not in active_nodes:
            continue
        active_nodes.remove(node)
        for neighbor in adj[node]:
            if neighbor in active_nodes:
                degree[neighbor] -= 1
                if degree[neighbor] < k:
                    queue.append(neighbor)
    
    # Eredmény kiírása
    result = sorted(active_nodes)
    print(len(result))
    if result:
        print(" ".join(map(str, result)))
    
if __name__ == "__main__":
    # Beolvasás
    n, m, k = map(int, sys.stdin.readline().split())
    edges = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
    
    find_max_k_secure_subnetwork(n, m, k, edges)
RészfeladatÖsszpontTesztVerdiktIdőMemória
base38/50
1Elfogadva0/019ms3372 KiB
2Futási hiba0/0170ms32000 KiB
3Elfogadva2/218ms3632 KiB
4Elfogadva2/218ms3816 KiB
5Elfogadva2/219ms3644 KiB
6Elfogadva2/218ms3588 KiB
7Elfogadva2/218ms3628 KiB
8Elfogadva2/218ms3632 KiB
9Elfogadva2/218ms3636 KiB
10Elfogadva2/235ms6468 KiB
11Elfogadva2/223ms4404 KiB
12Elfogadva2/232ms6196 KiB
13Elfogadva3/321ms4660 KiB
14Elfogadva3/339ms7856 KiB
15Elfogadva3/352ms12588 KiB
16Futási hiba0/3160ms32000 KiB
17Elfogadva3/337ms7284 KiB
18Elfogadva3/382ms23128 KiB
19Futási hiba0/3137ms32000 KiB
20Futási hiba0/3209ms32000 KiB
21Futási hiba0/3155ms32000 KiB
22Elfogadva3/318ms3440 KiB