Участник:StasFomin/Solutions/codechef/QLK03 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
* [[Codechef/QLK03]]
 
* [[Codechef/QLK03]]
<code-python>
+
 
 +
<source lang="python">
 
T = int(input())
 
T = int(input())
 
for _ in range(T):
 
for _ in range(T):
Строка 55: Строка 56:
  
 
     print(answer)
 
     print(answer)
</code-python>
+
</source>
 +
 
 +
{{checkme|[[Участник:StasFomin|StasFomin]] 18:58, 3 ноября 2021 (UTC)}}

Версия 18:58, 3 ноября 2021

T = int(input())
for _ in range(T):
    N, K = list(map(int, input().strip().split())) 
    A = [[] for _ in range(N+1)]       # for every vertex we find its neighbours
    edges = []
    colors = dict()
    startnode = 1
 
    for _ in range(K):
        v, w = list(map(int, input().strip().split()))      #  1 <= v <= N,  1 <= w <= N
        edges.append((v, w))
        A[v].append(w)
        A[w].append(v)
 
    new_startnode = 2
    queue = [startnode]
    explored = 1
    current_color = 1
    colors[startnode] = current_color
 
    while explored < N:
        while len(queue) > 0:             #  queue is not empty
            v = queue[0]
            current_color = -colors[v]
 
            for w in A[v]:
                if colors.get(w) == None:
                    colors[w] = current_color
                    queue.append(w)
                    explored += 1
 
            queue.pop(0)
 
 
        if explored < N:
            while colors.get(new_startnode) != None:    
                new_startnode += 1
 
            startnode = new_startnode
            queue.append(startnode)
            explored += 1
            current_color = 1
            colors[startnode] = current_color
 
 
 
    answer = 'possible'
    for e in edges:
        v, w = e
        if colors[v] == colors[w]:
            answer = 'impossible'
            break
 
    print(answer)

Check-me-animated.gif Решено: StasFomin 18:58, 3 ноября 2021 (UTC)