Introducción a grafos funcionales

#include <iostream>
#include <string>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
vector<int> move_result(const vector<int> &to_move) {
	cout << "next ";
	for (int i = 0; i < to_move.size() - 1; i++) { cout << to_move[i] << ' '; }
	cout << to_move.back() << endl;
 
	int group_num;
	std::cin >> group_num;
	vector<int> groups(10);
	for (int g = 0; g < group_num; g++) {
		std::string group;
		std::cin >> group;
		for (char i : group) { groups[i - '0'] = g; }
	}
	return groups;
}
 
int main() {
	move_result({0, 1});
	vector<int> groups = move_result({1});
	while (groups[0] != groups[1]) {
		move_result({0, 1});
		groups = move_result({1});
	}
 
	while (groups[2] != groups[1]) {
		groups = move_result({0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
	}
 
	cout << "done" << endl;
}

import java.io.*;
import java.util.*;
 
public class CoopGame {
	static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
 
	public static void main(String[] args) throws IOException {
		moveResult(new int[] {0, 1});
		int[] groups = moveResult(new int[] {1});
		while (groups[0] != groups[1]) {
			moveResult(new int[] {0, 1});
			groups = moveResult(new int[] {1});
		}
 
		while (groups[2] != groups[1]) {
			groups = moveResult(new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
		}
 
		System.out.println("done");
	}
 
	static int[] moveResult(int[] toMove) throws IOException {
		System.out.print("next ");
		for (int i = 0; i < toMove.length - 1; i++) {
			System.out.print(toMove[i] + " ");
		}
		System.out.println(toMove[toMove.length - 1]);
		System.out.flush();
 
		StringTokenizer groupST = new StringTokenizer(read.readLine());
		int groupNum = Integer.parseInt(groupST.nextToken());
		int[] groups = new int[10];
		for (int g = 0; g < groupNum; g++) {
			String group = groupST.nextToken();
			for (int i = 0; i < group.length(); i++) {
				groups[group.charAt(i) - '0'] = g;
			}
		}
		return groups;
	}
}

def move_result(to_move):
	"""
	Type annotations break the grader for some reason,
	so here's the signature of the function:
	move_result(to_move: Iterable[int]) -> list[int]
	"""
	print(f"next {' '.join(str(i) for i in to_move)}", flush=True)
 
	res = input().split()
	groups = [0 for _ in range(10)]
	for g in range(int(res[0])):
		for i in res[g + 1]:
			groups[int(i)] = g
	return groups
 
 
move_result([0, 1])
groups = move_result([1])
while groups[0] != groups[1]:
	move_result([0, 1])
	groups = move_result([1])
 
while groups[2] != groups[1]:
	groups = move_result(range(10))
 
print("done")

a = succ(x)
b = succ(succ(x))
 
while a != b:
	a = succ(a)
	b = succ(succ(b))

a = succ(x);
b = succ(succ(x));
 
while (a != b) {
	a = succ(a);
	b = succ(succ(b));
}

a = succ(x);
b = succ(succ(x));
 
while (a != b) {
	a = succ(a);
	b = succ(succ(b));
}

a = x
while a != b:
	a = succ(a)
	b = succ(b)
first = a

a = x;
while (a != b) {
	a = succ(a);
	b = succ(b);
}
first = a;

a = x;
while (a != b) {
	a = succ(a);
	b = succ(b);
}
first = a;

#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
vector<int> p;
vector<int> ans;
bool in_cycle = false;
 
void dfs(int n) {
	if (ans[n] != -2) {
		// it seems we've come back to something we've visited- a cycle!
		if (ans[n] == -1) {
			in_cycle = true;
			ans[n] = n;
		}
		return;  // either way, this one's already been processed
	}
 
	ans[n] = -1;  // set a marker for our dfs
 
	dfs(p[n]);
	// check if we're back at the initial cycle node
	if (ans[n] != -1) {
		// if so, now we're no longer in the cycle
		in_cycle = false;
	} else {
		// set our answer depending on if we're in a cycle or not
		ans[n] = in_cycle ? n : ans[p[n]];
	}
}
 
int main() {
	int n;
	std::cin >> n;
	p = vector<int>(n);
	for (int &i : p) {
		std::cin >> i;
		i--;
	}
 
	ans = vector<int>(n, -2);  // -2 is our initial no-answer value
	for (int i = 0; i < n; i++) {
		// in_cycle is always reset to false at the end of each DFS
		dfs(i);
	}
 
	for (int i = 0; i < n; i++) { cout << (ans[i] + 1) << " \n"[i == n - 1]; }
}

import java.io.*;
import java.util.*;
 
public class Badge {
	public static int[] p;
	public static int[] ans;
	public static boolean in_cycle;
 
	public static void dfs(int n) {
		if (ans[n] != -2) {
			// it seems we've come back to something we've visited- a cycle!
			if (ans[n] == -1) {
				in_cycle = true;
				ans[n] = n;
			}
			return;  // either way, this one's already been processed
		}
 
		ans[n] = -1;  // set a marker for our dfs
 
		dfs(p[n]);
		// check if we're back at the initial cycle node
		if (ans[n] != -1) {
			// if so, now we're no longer in the cycle
			in_cycle = false;
		} else {
			// set our answer depending on if we're in a cycle or not
			ans[n] = in_cycle ? n : ans[p[n]];
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
 
		int n = Integer.parseInt(reader.readLine());
		p = new int[n];
		StringTokenizer st = new StringTokenizer(reader.readLine());
		for (int i = 0; i < n; i++) { p[i] = Integer.parseInt(st.nextToken()) - 1; }
		reader.close();
 
		ans = new int[n];
		Arrays.fill(ans, -2);  // -2 is our initial no-answer value
		for (int i = 0; i < n; i++) {
			// in_cycle is always reset to false at the end of each DFS
			dfs(i);
		}
 
		for (int i = 0; i < n - 1; i++) { System.out.print((ans[i] + 1) + " "); }
		System.out.println(ans[n - 1] + 1);
	}
}

import sys
 
sys.setrecursionlimit(10**5)
 
n = int(input())
p = [int(i) - 1 for i in input().split()]
assert n == len(p)
 
 
def dfs(n: int) -> None:
	global in_cycle
	if ans[n] != -2:
		if ans[n] == -1:
			in_cycle = True
			ans[n] = n
 
		return
 
	ans[n] = -1
 
	dfs(p[n])
	if ans[n] != -1:
		in_cycle = False
	else:
		ans[n] = n if in_cycle else ans[p[n]]
 
 
in_cycle = False
ans = [-2 for _ in range(n)]
for i in range(n):
	dfs(i)
 
print(" ".join(str(i + 1) for i in ans))

#include <bits/stdc++.h>
using namespace std;
 
int n;
vector<int> adj, ans;
vector<vector<int>> radj;
 
void fill_radj(int x) {
	for (auto &child : radj[x]) {
		/*
		 * As all nodes in the cycle are processed in function floyd,
		 * the recursive call will only start at the nodes which
		 * combine the cycle with the acyclic part of the connected component
		 * where one of its outgoing arrows points to the node that is not
		 * processed yet.
		 */
		if (ans[child] == -1) {
			ans[child] = ans[x];
			fill_radj(child);
		}
	}
}
 
void floyd(int x) {
	int y = x;
	do {  // find a cycle using Floyd's algorithm
		x = adj[x];
		y = adj[adj[y]];
	} while (y != x);
	do {  // set ans[x] = x for all x along cycle
		ans[x] = x;
		x = adj[x];
	} while (y != x);
	do {  // set ans'es for all x not along cycle
		fill_radj(x);
		x = adj[x];
	} while (y != x);
}
 
int main() {
	cin >> n;
 
	adj.assign(n, -1);
	for (auto &e : adj) {
		cin >> e;
		e--;
	}
 
	/*
	 * For each node, we have to use a vector to store its children;
	 * at nodes combining the cycle with other parts of the connected component,
	 * there would be more than one outgoing arrow in the reversed adjacency
	 * list
	 */
	radj.assign(n, {});
	for (int i = 0; i < n; i++) radj[adj[i]].push_back(i);
 
	ans.assign(n, -1);
	// we run Floyd's algorithm for each connected component
	for (int i = 0; i < n; i++)
		if (ans[i] == -1) floyd(i);
 
	for (auto &a : ans) cout << a + 1 << " ";
}

import java.io.*;
import java.util.*;
 
public class Badge {
	static int[] adj;
	static int[] ans;
	/*
	 * For each node, we need a list to store its children; at nodes
	 * combining the cycle with other part of the connected component, there
	 * would be more than one outgoing arrow in the reversed adjacency list
	 */
	static List<List<Integer>> radj;
 
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 
		int n = Integer.parseInt(in.readLine());
		adj = new int[n];
		ans = new int[n];
		radj = new ArrayList<>();
 
		StringTokenizer st = new StringTokenizer(in.readLine());
		for (int i = 0; i < n; i++) {
			adj[i] = Integer.parseInt(st.nextToken()) - 1;
			ans[i] = -1;
			radj.add(new ArrayList<>());
		}
 
		for (int i = 0; i < n; i++) { radj.get(adj[i]).add(i); }
 
		for (int i = 0; i < n; i++) {
			// run Floyd's algorithm on every connected component
			if (ans[i] == -1) { floyd(i); }
		}
 
		for (int i = 0; i < n; i++) { System.out.print(ans[i] + 1 + " "); }
	}
 
	private static void floyd(int x) {
		int a = adj[x];
		int b = adj[adj[x]];
 
		// find a cycle using Floyd's algorithm
		while (a != b) {
			a = adj[a];
			b = adj[adj[b]];
		}
 
		// for each node a in the cycle, the answer ans[a] will be a as well
		do {
			ans[a] = a;
			a = adj[a];
		} while (a != b);
 
		// for each node a that has outgoing arrow(s) pointing to the acyclic
		// part we set their answers with fillRadj
		do {
			fillRadj(a);
			a = adj[a];
		} while (a != b);
	}
 
	private static void fillRadj(int x) {
		for (int child : radj.get(x)) {
			/*
			 * As all nodes in the cycle are processed in method floyd, the
			 * recursive call will only start at the nodes which combine the
			 * cycle with the acyclic part of the connected component, where one
			 * of its outgoing arrows points to the node that is not processed
			 * yet
			 */
			if (ans[child] == -1) {
				ans[child] = ans[x];
				fillRadj(child);
			}
		}
	}
}

n = int(input())
adj = [i - 1 for i in list(map(int, input().split()))]
radj = [[] for _ in range(n)]
ans = [-1] * n
 
 
def fill_radj(x: int) -> None:
	global ans
 
	"""
	As all nodes in the cycle are processed in function floyd,
	the recursive call will only start at the nodes which
	combine the cycle with the acyclic part of the connected component
	where one of its outgoing arrows points to the node that is not
	processed yet.
	"""
 
	for child in radj[x]:
		if ans[child] == -1:
			ans[child] = ans[x]
			fill_radj(child)
 
 
def floyd(x: int) -> None:
	global ans
	y = x
 
	# find cycle with floyd's
	while True:
		x = adj[x]
		y = adj[adj[y]]
 
		if y == x:
			break
 
	# set answer for the cycle
	while True:
		ans[x] = x
		x = adj[x]
 
		if y == x:
			break
 
	# set answer for students not in cycle
	while True:
		fill_radj(x)
		x = adj[x]
 
		if y == x:
			break
 
 
for i in range(n):
	radj[adj[i]].append(i)
 
for i in range(n):
	if ans[i] == -1:
		floyd(i)
 
print(" ".join(str(i + 1) for i in ans))

#include <bits/stdc++.h>
using namespace std;
 
vector<int> res;
vector<int> arr;
 
/*
 * fills up all vertices from curr to first_cycle,
 * whose answer has already been calculated
 */
void fill_up(int curr, int first_cycle) {
	while (curr != first_cycle) {
		res[curr] = res[first_cycle];
		curr = arr[curr];
	}
}
 
int floyd(int curr) {
	int a = arr[curr];
	int b = arr[arr[curr]];
	// find cycle using Floyd's algo
	while (a != b) {
		/*
		 * while finding cycle, if a node is found out to be already
		 * calculated, go to the fill_up function, where, the answer from
		 * vertex curr to this vertex a is ans[a]
		 */
		if (res[a] != -1) {
			fill_up(curr, a);
			return 0;
		}
		a = arr[a];
		b = arr[arr[b]];
	}
 
	a = curr;
	while (a != b) {
		a = arr[a];
		b = arr[b];
	}
 
	int cycle_first = a;
	a = curr;
	while (a != cycle_first) {
		res[a] = cycle_first;
		a = arr[a];
	}
 
	a = cycle_first;
	// for each node in the cycle, the answer would be itself
	do {
		res[a] = a;
		a = arr[a];
	} while (a != cycle_first);
 
	return 0;
}
 
int main() {
	int n;
	cin >> n;
	arr.resize(n + 1);
	for (int i = 1; i <= n; i++) { cin >> arr[i]; }
 
	res.resize(n + 1, -1);
	for (int i = 1; i <= n; i++) {
		if (res[i] == -1) { floyd(i); }
	}
 
	for (int i = 1; i <= n; i++) { cout << res[i] << " \n"[i == n]; }
}

import java.io.*;
import java.util.*;
 
public class Badge {
	static int[] ans;
	static int[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader x = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(x.readLine());
		int n = Integer.parseInt(st.nextToken());
		arr = new int[n + 1];
		st = new StringTokenizer(x.readLine());
		for (int i = 1; i <= n; i++) { arr[i] = Integer.parseInt(st.nextToken()); }
 
		ans = new int[n + 1];
		Arrays.fill(ans, -1);
		for (int i = 1; i <= n; i++) {
			if (ans[i] == -1) { floyd(i); }
		}
 
		StringBuilder output = new StringBuilder();
		for (int i = 1; i <= n; i++) { output.append(ans[i]).append(" "); }
		output.setLength(output.length() - 1);
		System.out.println(output);
	}
 
	/**
	 * fills up all vertices from curr to firstCycle,
	 * whose answer has already been calculated
	 */
	static void fillUp(int curr, int firstCycle) {
		while (curr != firstCycle) {
			ans[curr] = ans[firstCycle];
			curr = arr[curr];
		}
	}
 
	static int floyd(int curr) {
		int a = arr[curr];
		int b = arr[arr[curr]];
		// find cycle using Floyd's algo
		while (a != b) {
			/*
			 * while finding cycle, if a node is found out to be already
			 * calculated, go to the fillUp function, where, the answer from
			 * vertex curr to this vertex a is ans[a]
			 */
			if (ans[a] != -1) {
				fillUp(curr, a);
				return 0;
			}
			a = arr[a];
			b = arr[arr[b]];
		}
		a = curr;
		while (a != b) {
			a = arr[a];
			b = arr[b];
		}
		int cycleFirst = a;
		a = curr;
 
		while (a != cycleFirst) {
			ans[a] = cycleFirst;
			a = arr[a];
		}
		a = cycleFirst;
		// for each node in the cycle, the answer would be itself
		do {
			ans[a] = a;
			a = arr[a];
		} while (a != cycleFirst);
 
		return 0;
	}
}

def fill_up(curr: int, first_cycle: int):
	"""
	Fills up all vertices from curr to first_cycle,
	whose answer has already been calculated.
	"""
	while curr != first_cycle:
		res[curr] = res[first_cycle]
		curr = arr[curr]
 
 
def floyd(curr: int):
	a = arr[curr]
	b = arr[arr[curr]]
 
	# Find cycle using Floyd's cycle-finding algorithm
	while a != b:
		if res[a] != -1:
			"""
			While finding cycle, if a node is found to be already
			calculated, go to the fill_up function where the answer
			from vertex curr to this vertex a is res[a].
			"""
			fill_up(curr, a)
			return
 
		a = arr[a]
		b = arr[arr[b]]
 
	a = curr
	while a != b:
		a = arr[a]
		b = arr[b]
 
	cycle_first = a
	a = curr
	while a != cycle_first:
		res[a] = cycle_first
		a = arr[a]
 
	# For each node in the cycle, the answer would be itself
	a = cycle_first
	while True:
		res[a] = a
		a = arr[a]
		if a == cycle_first:
			break
 
 
n = int(input())
 
arr = list(map(int, input().split()))
arr = [0] + arr
res = [-1] * (n + 1)
 
for i in range(1, n + 1):
	if res[i] == -1:
		floyd(i)
 
print(*res[1:])

bool visited[MAXN];
bool on_stack[MAXN];
int number_of_cycles = 0;
int next_node[MAXN];
 
void dfs(int n) {
	visited[n] = on_stack[n] = true;
	int u = next_node[n];
	if (on_stack[u]) {
		number_of_cycles++;
	} else if (!visited[u]) {
		dfs(u);
	}
	on_stack[n] = false;
}
 
int main() {
	// read input, etc
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) { dfs(i); }
	}
}

import java.io.*;
import java.util.*;
 
public class CountCycles {
	static boolean[] visited = new boolean[MAXN];
	static boolean[] onStack = new boolean[MAXN];
	static int numberOfCycles = 0;
	static int[] nextNode = new int[MAXN];
 
	public static void main(String[] args) throws IOException {
		// Take in input
		for (int i = 1; i != N; i++) {
			if (!visited[i]) { dfs(i); }
		}
	}
 
	public static void dfs(int n) {
		visited[n] = onStack[n] = true;
		int u = nextNode[n];
		if (onStack[u]) {
			numberOfCycles++;
		} else if (!visited[u]) {
			dfs(u);
		}
		onStack[n] = false;
	}
}

vis = [False] * MAXN
on_stack = [False] * MAXN
next_node = [0] * MAXN
number_of_cycles = 0
 
 
def dfs(n: int) -> None:
	global number_of_cycles
	vis[n] = on_stack[n] = True
 
	if on_stack[next_node[n]]:
		number_of_cycles += 1
	elif not vis[next_node[n]]:
		dfs(next_node[n])
 
	on_stack[n] = 0
 
 
# read input, etc.
for i in range(MAXN):
	if not vis[i]:
		dfs(i)