結果

問題 No.1436 Rgaph
ユーザー lam6er
提出日時 2025-04-09 20:57:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,193 bytes
コンパイル時間 401 ms
コンパイル使用メモリ 82,808 KB
実行使用メモリ 72,920 KB
最終ジャッジ日時 2025-04-09 20:58:52
合計ジャッジ時間 5,488 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    edges = []
    for _ in range(M):
        A, B = map(int, sys.stdin.readline().split())
        edges.append((A-1, B-1))  # 0-based
    
    # Check strong connectivity using Kosaraju's algorithm
    # Build reversed graph
    adj = [[] for _ in range(N)]
    rev_adj = [[] for _ in range(N)]
    for A, B in edges:
        adj[A].append(B)
        rev_adj[B].append(A)
    
    visited = [False] * N
    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(N):
        if not visited[u]:
            dfs(u)
    
    visited = [False] * N
    label = [0] * N
    current_label = 0
    
    while order:
        u = order.pop()
        if visited[u]:
            continue
        stack = [u]
        visited[u] = True
        component = []
        while stack:
            node = stack.pop()
            component.append(node)
            for v in rev_adj[node]:
                if not visited[v]:
                    visited[v] = True
                    stack.append(v)
        for node in component:
            label[node] = current_label
        current_label += 1
    
    if current_label != 1:
        print(-1)
        return
    
    # Check if the graph is bipartite
    color = [-1] * N
    is_bipartite = True
    q = deque()
    q.append(0)
    color[0] = 0
    while q and is_bipartite:
        u = q.popleft()
        for v in adj[u]:
            if color[v] == -1:
                color[v] = color[u] ^ 1
                q.append(v)
            elif color[v] == color[u]:
                is_bipartite = False
                break
    if not is_bipartite:
        # Check if there's an odd-length cycle
        # In this case, we can construct the answer
        ans = []
        for i in range(M):
            ans.append('R' if i % 2 == 0 else 'G')
        print(''.join(ans))
        return
    else:
        # Bipartite graph
        # For all edges, check if they cross partitions
        ans = []
        for A, B in edges:
            if color[A] != color[B]:
                ans.append('R')
            else:
                ans.append('G')
        # Verify if this works for all u, v
        # The bipartite graph must have even paths between nodes of the same color
        # However, since it's strongly connected, bipartition implies that all paths between same color are even-length
        # So this coloring should work
        # But need to check if all u to v have a path with even length
        # However, for bipartition, same color nodes must have even path lengths
        print(''.join(ans))
        return
    
    # If none of the above
    print(-1)

if __name__ == "__main__":
    main()
0