【算法通关指南：数据结构和算法篇 】链表相关算法题：3. 队列安排，4.约瑟夫问题

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int pre[N];
int ne[N];
int mp[N]; // mp[i] 表⽰ i 这个同学是否已经出队

int main()
{
	int n;
	cin >> n;

	ne[0] = 1;
	mp[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		int k, p;
		cin >> k >> p;

		if (p == 0)
		{
			pre[i] = pre[k];
			ne[i] = k;

			ne[pre[k]] = i;
			pre[k] = i;
			mp[i] = 1;
		}
		else if (p == 1)
		{
			pre[i] = k;
			ne[i] = ne[k];

			pre[ne[k]] = i;
			ne[k] = i;
			mp[i] = 1;
		}
	}


	int m;
	cin >> m;

	for (int i = 1; i <= m; i++)
	{
		int x;
		cin >> x;

		if (mp[x] == 0)  // 如果 x 已经被删除，忽视这条指令 
			continue;

		ne[pre[x]] = ne[x];
		pre[ne[x]] = pre[x];
		mp[x] = 0;
	}

	for (int i = ne[0]; i; i = ne[i])
		cout << i << " ";
	return 0;
}

#include <iostream>
using namespace std;
const int N = 110;
int ne[N];

int main()
{
	int n, m;
	cin >> n >> m;

	// 创建循环链表
	for (int i = 1; i < n; i++)
		ne[i] = i + 1;
	ne[n] = 1;

	// 模拟约瑟夫游戏的过程 
	int t = n;
	for (int i = 1; i <= n; i++)  // 执行n次出圈操作
	{
		for (int i = 1; i < m; i++)  // 让 t 向后移动 m - 1 次
			t = ne[t];

		cout << ne[t] << " ";
		ne[t] = ne[ne[t]];
	}
	return 0;
}