AtCoder Regular Contest 079 - Namori Grundy

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-----
4
2 3 4 1

-----Sample Output-----
POSSIBLE

The assignment is possible: {a_i} = {0, 1, 0, 1} or {a_i} = {1, 0, 1, 0}.

Difficulty: VERY_HARD

Starter code:

Solutions:
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')
	return

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')
	return
n = s2
for g in G:
	if g[0] == n:
		n = g[1]
	else:
		n = g[0]
if n == s1:
	print('POSSIBLE')
	return
print('IMPOSSIBLE')


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')
	return
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')
		return
print('IMPOSSIBLE')


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')
	return
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')
	return
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')
	return
print('IMPOSSIBLE')


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from collections import deque
	input = sys.stdin.readline
	N = int(input())
	P = list(map(int, input().split()))
	adj = [[] for _ in range(N + 1)]
	adj_directed = [[] for _ in range(N + 1)]
	adj_rev = [[] for _ in range(N + 1)]
	out = [0] * (N + 1)
	for (i, p) in enumerate(P):
		adj_directed[p].append(i + 1)
		adj[p].append(i + 1)
		adj[i + 1].append(p)
		adj_rev[i + 1].append(p)
		out[p] += 1
	que = deque()
	que.append(1)
	seen = [-1] * (N + 1)
	seen[1] = 0
	par = [-1] * (N + 1)
	back_from = -1
	back_to = -1
	while que:
		v = que.popleft()
		for u in adj[v]:
			if seen[u] == -1:
				seen[u] = seen[v] + 1
				que.append(u)
				par[u] = v
			elif par[v] != u:
				if P[v - 1] == u:
					back_from = u
					back_to = v
					out[u] -= 1
	G = [-1] * (N + 1)
	for v in range(1, N + 1):
		if out[v] == 0:
			que.append(v)
	while que:
		v = que.popleft()
		M = set()
		for u in adj_directed[v]:
			if v == back_from and u == back_to:
				continue
			M.add(G[u])
		for i in range(N + 1):
			if i not in M:
				G[v] = i
				break
		for u in adj_rev[v]:
			if v == back_to and u == back_from:
				continue
			out[u] -= 1
			if out[u] == 0:
				que.append(u)
	if G[back_from] != G[back_to]:
		print('POSSIBLE')
		return
	cycle = set()
	v = back_from
	while v > 0:
		cycle.add(v)
		v = par[v]
	v = back_to
	while v > 0:
		cycle.add(v)
		v = par[v]
	v = back_from
	seen = {v}
	while True:
		M = set()
		for u in adj_directed[v]:
			M.add(G[u])
		for i in range(N + 1):
			if i not in M:
				if G[v] == i:
					print('POSSIBLE')
					return
				G[v] = i
				break
		fin = 1
		for u in adj_rev[v]:
			if u in cycle and u not in seen:
				v = u
				seen.add(u)
				fin = 0
				break
		if fin:
			break
	print('IMPOSSIBLE')

def __starting_point():
	main()
__starting_point()


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([int(x) - 1 for x in 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')


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
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)
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)