Problem:
 Score : 800 points    Problem Statement There is a directed graph with N vertices and N edges. The vertices are numbered 1, 2, ..., N .  The graph has the following N edges: (p_1, 1), (p_2, 2), ..., (p_N, N) , and the graph is weakly connected. Here, an edge from Vertex u to Vertex v is denoted by (u, v) , and a weakly connected graph is a graph which would be connected if each edge was bidirectional.  We would like to assign a value to each of the vertices in this graph so that the following conditions are satisfied. Here, a_i is the value assigned to Vertex i .   Each a_i is a non-negative integer.  For each edge (i, j) , a_i \neq a_j holds.  For each i and each integer x(0 ≤ x < a_i) , there exists a vertex j such that the edge (i, j) exists and x = a_j holds.   Determine whether there exists such an assignment.      Constraints  2 ≤ N ≤ 200  000  1 ≤ p_i ≤ N  p_i \neq i  The graph is weakly connected.         Input Input is given from Standard Input in the following format:  N  p_1  p_2 ... p_N       Output If the assignment is possible, print POSSIBLE ; otherwise, print IMPOSSIBLE .        Sample Input 1 4
2 3 4 1      Sample Output 1 POSSIBLE  The assignment is possible: { a_i } = { 0, 1, 0, 1 } or { a_i } = { 1, 0, 1, 0 }.       Sample Input 2 3
2 3 1      Sample Output 2 IMPOSSIBLE       Sample Input 3 4
2 3 1 1      Sample Output 3 POSSIBLE  The assignment is possible: { a_i } = { 2, 0, 1, 0 }.       Sample Input 4 6
4 5 6 5 6 4      Sample Output 4 IMPOSSIBLE

Solution (Python):
from collections import deque

N=int(input())
IN=[[] for i in range(N)]
OUT=[-1 for i in range(N)]
p=list(map(int,input().split()))
for i in range(N):
    IN[p[i]-1].append(i)
    OUT[i]=p[i]-1

deg=[len(IN[i]) for i in range(N)]

deq=deque([v for v in range(N) if deg[v]==0])
res=[]
while deq:
    v=deq.popleft()
    res.append(v)
    deg[OUT[v]]-=1
    if deg[OUT[v]]==0:
        deq.append(OUT[v])

if len(res)==N:
    print("POSSIBLE")
    exit()

start=-1
for i in range(N):
    if deg[i]>0:
        start=i
        break

cycle=[start]
while True:
    nv=OUT[cycle[-1]]
    if nv!=start:
        cycle.append(nv)
    else:
        break


dp=[-1]*N
for v in res:
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break

m0=-1
m1=-1
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
for i in range(len(mex)):
    if not mex[i]:
        if m0==-1:
            m0=i
        else:
            m1=i
            break


dp[start]=m0
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
check=-1
for i in range(len(mex)):
    if not mex[i]:
        check=i
        break
if check==m0:
    print("POSSIBLE")
    exit()

for v in cycle:
    dp[v]=-1


dp[start]=m1
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[start])+1:
        mex[dp[pv]]=True
check=-1
for i in range(len(mex)):
    if not mex[i]:
        check=i
        break
if check==m1:
    print("POSSIBLE")
    exit()

print("IMPOSSIBLE")

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
p = list(map(int, input().split()))
c = [[] for _ in range(n)]
is_leaf = [True for _ in range(n)]
for i in range(n):
	p[i] -= 1
	c[p[i]].append(i)
	is_leaf[p[i]] = False

if sum(is_leaf) == 0:
	if n%2 == 0:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")
	sys.exit()

for i in range(n):
	if is_leaf[i]:
		cur = i
		break

visited_set = {cur}
visited_list = [cur]
while p[cur] not in visited_set:
	visited_list.append(p[cur])
	visited_set.add(p[cur])
	cur = p[cur]

root = p[cur]

grundy = [-1 for _ in range(n)]
g_set = [set() for _ in range(n)]

def dfs(x):
	res = 0
	for v in c[x]:
		dfs(v)
		g_set[x].add(grundy[v])
	while res in g_set[x]:
		res += 1
	grundy[x] = res
	return res

loop = [False for _ in range(n)]
loop[root] = True
ind = len(visited_list)-1
while visited_list[ind] != root:
	loop[visited_list[ind]] = True
	ind -= 1


for i in range(n):
	if loop[i]:
		for x in c[i]:
			if not loop[x]:
				dfs(x)
				g_set[i].add(grundy[x])

cand = []
num = 0
while num in g_set[root]:
	num += 1
cand.append(num)
num += 1
while num in g_set[root]:
	num += 1
cand.append(num)

for x in cand:
	cur = root
	grundy[root] = x
	while True:
		num = 0
		while num in g_set[p[cur]] or num == grundy[cur]:
			num += 1
		grundy[p[cur]] = num
		if p[cur] == root:
			break
		cur = p[cur]
	if grundy[root] == x:
		
		print("POSSIBLE")
		sys.exit()

print("IMPOSSIBLE")

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
p = list(map(int, input().split()))
c = [[] for _ in range(n)]
is_leaf = [True for _ in range(n)]
for i in range(n):
	p[i] -= 1
	c[p[i]].append(i)
	is_leaf[p[i]] = False

if sum(is_leaf) == 0:
	if n%2 == 0:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")
	sys.exit()

for i in range(n):
	if is_leaf[i]:
		cur = i
		break

visited_set = {cur}
visited_list = [cur]
while p[cur] not in visited_set:
	visited_list.append(p[cur])
	visited_set.add(p[cur])
	cur = p[cur]

root = p[cur]

grundy = [-1 for _ in range(n)]
g_set = [set() for _ in range(n)]

def dfs(x):
	res = 0
	for v in c[x]:
		dfs(v)
		g_set[x].add(grundy[v])
	while res in g_set[x]:
		res += 1
	grundy[x] = res
	return res

loop = [False for _ in range(n)]
loop[root] = True
ind = len(visited_list)-1
while visited_list[ind] != root:
	loop[visited_list[ind]] = True
	ind -= 1


for i in range(n):
	if loop[i]:
		for x in c[i]:
			if not loop[x]:
				dfs(x)
				g_set[i].add(grundy[x])

cand = []
num = 0
while num in g_set[root]:
	num += 1
cand.append(num)
num += 1
while num in g_set[root]:
	num += 1
cand.append(num)

for x in cand:
	cur = root
	grundy[root] = x
	while True:
		num = 0
		while num in g_set[p[cur]] or num == grundy[cur]:
			num += 1
		grundy[p[cur]] = num
		if p[cur] == root:
			break
		cur = p[cur]
	if grundy[root] == x:
		
		print("POSSIBLE")
		sys.exit()

print("IMPOSSIBLE")

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
p = list(map(int, input().split()))
c = [[] for _ in range(n)]
is_leaf = [True for _ in range(n)]
for i in range(n):
	p[i] -= 1
	c[p[i]].append(i)
	is_leaf[p[i]] = False

if sum(is_leaf) == 0:
	if n%2 == 0:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")
	sys.exit()

for i in range(n):
	if is_leaf[i]:
		cur = i
		break

visited_set = {cur}
visited_list = [cur]
while p[cur] not in visited_set:
	visited_list.append(p[cur])
	visited_set.add(p[cur])
	cur = p[cur]

root = p[cur]

grundy = [-1 for _ in range(n)]
g_set = [set() for _ in range(n)]

def dfs(x):
	res = 0
	for v in c[x]:
		dfs(v)
		g_set[x].add(grundy[v])
	while res in g_set[x]:
		res += 1
	grundy[x] = res
	return res

loop = [False for _ in range(n)]
loop[root] = True
ind = len(visited_list)-1
while visited_list[ind] != root:
	loop[visited_list[ind]] = True
	ind -= 1


for i in range(n):
	if loop[i]:
		for x in c[i]:
			if not loop[x]:
				dfs(x)
				g_set[i].add(grundy[x])

cand = []
num = 0
while num in g_set[root]:
	num += 1
cand.append(num)
num += 1
while num in g_set[root]:
	num += 1
cand.append(num)

for x in cand:
	cur = root
	grundy[root] = x
	while True:
		num = 0
		while num in g_set[p[cur]] or num == grundy[cur]:
			num += 1
		grundy[p[cur]] = num
		if p[cur] == root:
			break
		cur = p[cur]
	if grundy[root] == x:
		
		print("POSSIBLE")
		sys.exit()

print("IMPOSSIBLE")

Solution (Python):
import sys
from itertools import chain
readline = sys.stdin.readline


def scc(Edge):
    N = len(Edge)
    Edgeinv = [[] for _ in range(N)]
    for vn in range(N):
        for vf in Edge[vn]:
            Edgeinv[vf].append(vn)
    
    used = [False]*N
    dim = [len(Edge[i]) for i in range(N)]
    order = []
    for st in range(N):
        if not used[st]:
            stack = [st, 0]
            while stack:
                vn, i = stack[-2], stack[-1]   
                if not i and used[vn]:
                    stack.pop()
                    stack.pop()
                else:
                    used[vn] = True
                    if i < dim[vn]:
                        stack[-1] += 1
                        stack.append(Edge[vn][i])
                        stack.append(0)
                    else:
                        stack.pop()
                        order.append(stack.pop())
    res = [None]*N
    used = [False]*N
    cnt = -1
    for st in order[::-1]:
        if not used[st]:
            cnt += 1
            stack = [st]
            res[st] = cnt
            used[st] = True
            while stack:
                vn = stack.pop()
                for vf in Edgeinv[vn]:
                    if not used[vf]:
                        used[vf] = True
                        res[vf] = cnt
                        stack.append(vf)
    M = cnt+1
    components = [[] for _ in range(M)]
    for i in range(N):
        components[res[i]].append(i)
    tEdge = [[] for _ in range(M)]
    teset = set()
    for vn in range(N):
        tn = res[vn]
        for vf in Edge[vn]:
            tf = res[vf]
            if tn != tf and tn*M + tf not in teset:
                teset.add(tn*M + tf)
                tEdge[tn].append(tf)
    return res, components, tEdge

N = int(readline())
P = list(map(lambda x: int(x)-1, readline().split()))

Edge = [[] for _ in range(N)]
for i in range(N):
    Edge[P[i]].append(i)

R, Com, _ = scc(Edge)

Lord = list(chain(*Com[::-1]))
val = [None]*N
for vn in Lord:
    if not R[vn]:
        break
    lvn = len(Edge[vn]) + 1
    res = [0]*lvn
    for vf in Edge[vn]:
        if val[vf] < lvn:
            res[val[vf]] += 1
    
    for k in range(lvn):
        if not res[k]:
            val[vn] = k
            break

st = Lord[-1]
lst = len(Edge[st]) + 2
res = [0]*lst
for vf in Edge[st]:
    if val[vf] is None:
        continue
    if val[vf] < lst:
        res[val[vf]] += 1
mc = []
for k in range(lst):
    if not res[k]:
        mc.append(k)

vn = st
Ls = []
while vn is not None:
    for vf in Edge[vn]:
        if R[vf]:
            continue
        if vf == st:
            vn = None
        else:
            Ls.append(vf)
            vn = vf

Ls.reverse()

ans = False
for idx in range(2):
    vc = val[:]
    vc[st] = mc[idx]
    for vn in Ls:
        lvn = len(Edge[vn])+1
        res = [0]*lvn
        for vf in Edge[vn]:
            if vc[vf] < lvn:
                res[vc[vf]] += 1
        
        for k in range(lvn):
            if not res[k]:
                vc[vn] = k
                break
    
    for vn in range(N):
        res = [False]*vc[vn]
        for vf in Edge[vn]:
            if vc[vn] == vc[vf]:
                break
            if vc[vf] < vc[vn]:
                res[vc[vf]] = True
        else:
            if not all(res):
                break
            continue
        break
    else:
        ans = True
    if ans:
        break
print('POSSIBLE' if ans else 'IMPOSSIBLE')

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・pseudo-tree graph
・in_deg = 1が保証されているので、向きの揃ったcycleがある
・1箇所の2択を決めれば全部決まる
"""

N = int(readline())
parent = [0] + list(map(int,read().split()))

child = [[] for _ in range(N+1)]
for i,x in enumerate(parent):
    child[x].append(i)

out_deg = [len(x) for x in child]

out_deg

G = [-1] * (N+1)



stack = [i for i,x in enumerate(out_deg) if not x]
while stack:
    x = stack.pop()
    se = set(G[c] for c in child[x])
    g = 0
    while g in se:
        g += 1
    G[x] = g
    p = parent[x]
    out_deg[p] -= 1
    if not out_deg[p]:
        stack.append(p)

"""
・grundy数の候補は2種。
・片方決め打って計算。2周grundy数を計算してstableになっていればよい。
"""

for i,x in enumerate(out_deg[1:],1):
    if x==1:
        root = i
        break

cycle_len = sum(out_deg[1:])

is_stable = False
x = root
for _ in range(cycle_len*2+10):
    se = set(G[c] for c in child[x])
    g = 0
    while g in se:
        g += 1
    if g == G[x]:
        is_stable = True
        break
    G[x] = g
    x = parent[x]

answer = 'POSSIBLE' if is_stable else 'IMPOSSIBLE'
print(answer)

Solution (Python):
from collections import defaultdict
import heapq as hq


def helper(n):
    q = child_L[n]
    del child_L[n]

    hq.heapify(q)
    i = 0
    while q:
        t = hq.heappop(q)
        if i < t:
            break
        else:
            i += (i == t)

    j = i + 1
    while q:
        t = hq.heappop(q)
        if j < t:
            break
        else:
            j += (j == t)

    return (i, j)


if __name__ == '__main__':

    N = int(input())
    P = list(map(lambda x: int(x) - 1, input().split()))
    
    D = [0] * N
    for p in P:
        D[p] += 1
    
    child_L = defaultdict(list)
    
    S = [p for p in range(N) if D[p] == 0]

    L = [None] * N

    while S:
        
        n = S.pop()

        q = child_L[n]
        
        del child_L[n]

        
        hq.heapify(q)
        i = 0
        while q:
            t = hq.heappop(q)
            if i < t:
                break
            else:
                i += (i == t)

        L[n] = i
        
        m = P[n]
        
        child_L[m].append(i)
        D[m] -= 1
        if D[m] == 0:
            S.append(m)

    
    
    try:
        start = D.index(1)
    except ValueError:
        print('POSSIBLE')
        exit()

    s1, s2 = helper(start)
    G = []
    n = P[start]
    while n != start:
        G.append(helper(n))
        n = P[n]

    

    
    
    n = s1
    for g in G:
        if g[0] == n:
            n = g[1]
        else:
            n = g[0]
    if n != s1:
        print('POSSIBLE')
        exit()

    
    n = s2
    for g in G:
        if g[0] == n:
            n = g[1]
        else:
            n = g[0]
    if n == s1:
        print('POSSIBLE')
        exit()

    print('IMPOSSIBLE')

Solution (Python):

from collections import defaultdict
import heapq as hq

N = int(input())
P = list(map(lambda x:int(x)-1,input().split()))
D = [0]*N
for p in P:
  D[p] += 1

child_L = defaultdict(list)

S = [p for p in range(N) if D[p] == 0]
L = [None]*N

while S:
  n = S.pop()

  q = child_L[n]
  del child_L[n]

  hq.heapify(q)
  i = 0
  while q:
    t = hq.heappop(q)
    if i < t:
      break
    else:
      i += (i==t)
  
  L[n] = i
  m = P[n]
  child_L[m].append(i)
  D[m] -= 1
  if D[m] == 0:
    S.append(m)


try:
  start = D.index(1)
except ValueError:
  print('POSSIBLE')
  exit()

def helper(n):
  q = child_L[n]
  del child_L[n]
  
  hq.heapify(q)
  i = 0
  while q:
    t = hq.heappop(q)
    if i < t:
      break
    else:
      i += (i==t)

  j = i+1
  while q:
    t = hq.heappop(q)
    if j < t:
      break
    else:
      j += (j==t)

  return (i,j)


s1,s2 = helper(start)
G = []
n = P[start]
while n != start:
  G.append(helper(n))
  n = P[n]


del N,P,D,child_L,S,L




n = s1
for g in G:
  if g[0] == n:
    n = g[1]
  else:
    n = g[0]
if n != s1:
  print('POSSIBLE')
  exit()


n = s2
for g in G:
  if g[0] == n:
    n = g[1]
  else:
    n = g[0]
if n == s1:
  print('POSSIBLE')
  exit()

print('IMPOSSIBLE')