148772025-02-05 21:46:32feheristvanHálózati biztonság (50)python3Runtime error 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)
SubtaskSumTestVerdictTimeMemory
base38/50
1Accepted0/019ms3372 KiB
2Runtime error0/0170ms32000 KiB
3Accepted2/218ms3632 KiB
4Accepted2/218ms3816 KiB
5Accepted2/219ms3644 KiB
6Accepted2/218ms3588 KiB
7Accepted2/218ms3628 KiB
8Accepted2/218ms3632 KiB
9Accepted2/218ms3636 KiB
10Accepted2/235ms6468 KiB
11Accepted2/223ms4404 KiB
12Accepted2/232ms6196 KiB
13Accepted3/321ms4660 KiB
14Accepted3/339ms7856 KiB
15Accepted3/352ms12588 KiB
16Runtime error0/3160ms32000 KiB
17Accepted3/337ms7284 KiB
18Accepted3/382ms23128 KiB
19Runtime error0/3137ms32000 KiB
20Runtime error0/3209ms32000 KiB
21Runtime error0/3155ms32000 KiB
22Accepted3/318ms3440 KiB