結果

問題 No.1436 Rgaph
ユーザー lam6er
提出日時 2025-03-20 20:57:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,626 bytes
コンパイル時間 409 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 73,704 KB
最終ジャッジ日時 2025-03-20 20:57:31
合計ジャッジ時間 5,165 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    edges = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]

    # Check strong connectivity using Kosaraju's algorithm
    adj = [[] for _ in range(N+1)]  # 1-based
    adj_rev = [[] for _ in range(N+1)]
    for a, b in edges:
        adj[a].append(b)
        adj_rev[b].append(a)
    
    visited = [False] * (N+1)
    order = []
    def dfs(u):
        stack = [(u, False)]
        while stack:
            node, processed = stack.pop()
            if processed:
                order.append(node)
                continue
            if visited[node]:
                continue
            visited[node] = True
            stack.append((node, True))
            for v in adj[node]:
                if not visited[v]:
                    stack.append((v, False))
    for u in range(1, N+1):
        if not visited[u]:
            dfs(u)
    
    visited = [False] * (N+1)
    component = [0]*(N+1)
    label = 0
    for u in reversed(order):
        if visited[u]:
            continue
        label +=1
        stack = [u]
        visited[u] = True
        while stack:
            node = stack.pop()
            component[node] = label
            for v in adj_rev[node]:
                if not visited[v]:
                    visited[v] = True
                    stack.append(v)
    if label != 1:
        print(-1)
        return
    
    # Check bipartition of undirected graph
    color = [ -1 ] * (N+1)
    is_bipartite = True
    for u in range(1, N+1):
        if color[u] == -1:
            queue = deque()
            queue.append(u)
            color[u] = 0
            while queue:
                v = queue.popleft()
                for a, b in edges:
                    if a == v or b == v:
                        nb = a if b == v else b
                        if color[nb] == -1:
                            color[nb] = color[v] ^ 1
                            queue.append(nb)
                        elif color[nb] == color[v]:
                            is_bipartite = False
                            break
                if not is_bipartite:
                    break
            if not is_bipartite:
                break
    if is_bipartite:
        print(-1)
        return
    
    # If not bipartite and strongly connected, output alternate R and G
    s = []
    for i in range(M):
        if i %2 ==0:
            s.append('R')
        else:
            s.append('G')
    print(''.join(s))
    
if __name__ == "__main__":
    main()
0