結果

問題 No.3056 Disconnected Coloring
ユーザー V_Melville
提出日時 2025-03-14 22:05:37
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 2,917 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 83,456 KB
最終ジャッジ日時 2025-03-14 22:05:53
合計ジャッジ時間 10,206 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 7 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict, deque

sys.setrecursionlimit(1 << 25)

def input():
    return stdin.readline()

def main():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v = map(int, input().split())
        edges.append((u-1, v-1))  # 0-based

    if M % 2 != 0:
        print(-1)
        return

    adj = [[] for _ in range(N)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))

    # Find all bridges using Tarjan's algorithm
    bridges = set()
    visited = [False] * N
    disc = [float('inf')] * N
    low = [float('inf')] * N
    parent = [-1] * N
    time = 0

    def tarjan(u):
        nonlocal time
        visited[u] = True
        disc[u] = time
        low[u] = time
        time += 1
        for v, idx in adj[u]:
            if not visited[v]:
                parent[v] = (u, idx)
                tarjan(v)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.add(idx)
            elif v != parent[u][0] if parent[u] != -1 else True:
                low[u] = min(low[u], disc[v])

    tarjan(0)

    # Check each bridge if it's a critical bridge between 1 and N (0 and N-1 in 0-based)
    critical_bridges = []
    for idx in bridges:
        u, v = edges[idx]
        # Remove the bridge and check connectivity between 0 and N-1
        temp_adj = [[] for _ in range(N)]
        for i, (a, b) in enumerate(edges):
            if i == idx:
                continue
            temp_adj[a].append(b)
            temp_adj[b].append(a)
        # BFS to check connectivity
        visited_bfs = [False] * N
        q = deque([0])
        visited_bfs[0] = True
        while q:
            node = q.popleft()
            if node == N-1:
                break
            for neighbor in temp_adj[node]:
                if not visited_bfs[neighbor]:
                    visited_bfs[neighbor] = True
                    q.append(neighbor)
        if not visited_bfs[N-1]:
            critical_bridges.append(idx)

    k = len(critical_bridges)
    if k == 0 or k % 2 != 0:
        print(-1)
        return

    # Prepare colors
    color = ['B'] * M
    # Color k/2 bridges as R and the other half as B
    half = k // 2
    cnt = 0
    for idx in critical_bridges:
        if cnt < half:
            color[idx] = 'R'
            cnt += 1
        else:
            color[idx] = 'B'

    # Now distribute the remaining edges
    remaining = M - k
    # Need remaining / 2 R and B
    need_r = (remaining) // 2
    need_b = (remaining) // 2
    # Iterate through all edges not in critical_bridges
    for i in range(M):
        if i in critical_bridges:
            continue
        if need_r > 0:
            color[i] = 'R'
            need_r -= 1
        else:
            color[i] = 'B'
    print(''.join(color))

main()
0