問題文を丁寧によむと、おおよそ DFS の話をしています。注意するべきは

• 今いる頂点と同じであれば遷移しないこと
• 辺には適切に優先順位がついていること

です。

それらに注意して DFS を実装すれば AC することができます。

計算量について不安になるかもしれませんが、ふつうの DFS と同様に、「一度訪れた頂点は、その瞬間に 訪問済み となり、 \(2\) 回以上訪れることはない」という事実に注意すれば、各辺は高々 \(1\) 回しか訪問しないため \(O(N + M)\) になります。

実装例

import sys
sys.setrecursionlimit(400000)

n, m = map(int, input().split())
c = list(map(int, input().split()))
e = [[] for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    e[u].append(v)

seen = [0] * n

def dfs(u):
    seen[u] = 1
    for v in e[u]:
        if seen[v]: continue
        if c[u] == c[v]: continue
        if c[u] != c[v]:
            dfs(v)

dfs(0)

if seen.count(0) == 0:
    print("COMPLETE")
else:
    print(*[x+1 for x in range(n) if seen[x] == 0])