题目一：
AC代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 设定一个最大的同学数量，这里最多能处理 100010 个同学
#define mx 100010// 造一个小房子，用来装每个同学的信息
// 这个小房子有三个房间
typedef struct {// 第一个房间存这个同学左边同学的编号int l;// 第二个房间存这个同学右边同学的编号int r;// 第三个房间就像一个小牌子，0 表示这个同学要喊出来，1 表示这个同学不喊int d;
} T;// 造一排这样的小房子，能装下最多 mx 个同学的信息
T t[mx];// 这个函数是用来把新同学安排到队伍里的
// i 是队伍里已经有的一个同学的编号
// k 是新同学的编号
// f 就像一个小指令，1 表示新同学要站在 i 同学的左边，其他数表示站在右边
void add(int i, int k, int f) {if (f == 1) {// 如果要站在左边// 先让新同学看看 i 同学右边是谁，然后新同学记住这个人，把他当成自己右边的人t[k].r = t[i].r;// 新同学再把 i 同学当成自己左边的人t[k].l = i;// 接着让 i 同学把新同学当成自己右边的人t[i].r = k;// 最后让原来 i 同学右边的人把新同学当成自己左边的人t[t[k].r].l = k;} else {// 如果要站在右边// 新同学先把 i 同学当成自己右边的人t[k].r = i;// 再看看 i 同学左边是谁，把这个人当成自己左边的人t[k].l = t[i].l;// 让 i 同学把新同学当成自己左边的人t[i].l = k;// 最后让原来 i 同学左边的人把新同学当成自己右边的人t[t[k].l].r = k;}
}int main() {// n 是一共有多少个同学// m 是有几个同学不能喊出来int n, m;// x 用来存输入里已有的同学编号// k 暂时没用，因为新同学编号是按顺序来的// f 是用来决定新同学站哪里的指令int x, k, f;// 从键盘上输入一共有多少个同学，把这个数存到 n 里scanf("%d", &n);// 有一个特殊的“虚拟同学”，编号是 0// 让这个“虚拟同学”的左边和右边都是自己t[0].r = 0;t[0].l = 0;// 把第一个同学，编号 1，安排到“虚拟同学”的左边add(0, 1, 1);// 从第二个同学开始，一个一个地把剩下的同学安排到队伍里for (int i = 2; i <= n; i++) {// 从键盘上输入一个已有的同学编号 x 和一个指令 fscanf("%d %d", &x, &f);// 把编号为 i 的新同学按照指令安排到队伍里add(x, i, f);}// 从键盘上输入有几个同学不能喊出来，把这个数存到 m 里scanf("%d", &m);// 一次一次地处理那些不能喊出来的同学while (m--) {// 从键盘上输入不能喊出来的同学的编号 xscanf("%d", &x);// 把这个同学对应的小牌子（d）翻成 1，表示他不能喊t[x].d = 1;}// 从“虚拟同学”右边的第一个同学开始，一个一个往后看for (int i = t[0].r; i; i = t[i].r) {// 如果这个同学的小牌子是 0，说明他能喊if (t[i].d == 0) {// 把这个同学的编号喊出来，后面再跟个空格printf("%d ", i);}}return 0;
}题解：
1.准备工作
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define mx 100010typedef struct {int l;int r;int d;
} T;T t[mx]; 常量 mx：我们先设定了一个最大的同学数量 mx，就好像我们提前准备了一个足够大的操场，最多能容纳 100010 个同学。
结构体 T：创建了一个结构体 T，它就像是每个同学的 “信息小卡片”。这个小卡片上有三个信息：l 记录这个同学左边同学的编号，r 记录右边同学的编号，d 就像一个小牌子，0 表示这个同学要参与展示（喊出编号），1 表示不参与。
结构体数组 t：有了小卡片，我们就造了一排这样的小卡片，最多能放 mx 张，用来记录每个同学的信息。
2.新同学加入队伍的函数
void add(int i, int k, int f) {if (f == 1) {t[k].r = t[i].r;t[k].l = i;t[i].r = k;t[t[k].r].l = k;} else {t[k].r = i;t[k].l = t[i].l;t[i].l = k;t[t[k].l].r = k;}
}这个 add 函数就是负责把新同学安排到队伍里的。
参数：i 是队伍里已经有的一个同学的编号，k 是新同学的编号，f 是一个指令。当 f 等于 1 时，新同学要站在 i 同学的左边；当 f 不等于 1 时，新同学站在 i 同学的右边。
操作过程：以新同学站在 i 同学左边为例，首先新同学要看看 i 同学右边是谁，然后把这个人当成自己右边的人；接着新同学把 i 同学当成自己左边的人；再让 i 同学把新同学当成自己右边的人；最后让原来 i 同学右边的人把新同学当成自己左边的人。这样新同学就成功站到 i 同学左边了。站在右边的操作类似。
3. 主函数开始安排同学
int main() {int n, m;int x, k, f;scanf("%d", &n);t[0].r = 0;t[0].l = 0;add(0, 1, 1); 读取同学总数：通过 scanf 从键盘输入一共有多少个同学，把这个数存到 n 里。
虚拟同学：有一个特殊的 “虚拟同学”，编号是 0。我们先让这个 “虚拟同学” 的左边和右边都指向自己，就像这个 “虚拟同学” 自己站成了一个圈。
第一个同学加入：调用 add 函数，把第一个同学（编号 1）安排到 “虚拟同学” 的左边。
4. 后续同学依次加入队伍
for (int i = 2; i <= n; i++) {scanf("%d %d", &x, &f);add(x, i, f);} 从第二个同学开始，一个一个地把剩下的同学安排到队伍里。每次从键盘输入一个已有的同学编号 x 和一个指令 f，然后调用 add 函数把编号为 i 的新同学按照指令安排到队伍里。
5. 让部分同学 “沉默”
scanf("%d", &m);while (m--) {scanf("%d", &x);t[x].d = 1;} 读取 “沉默” 同学数量：从键盘输入有几个同学不能参与展示（要 “沉默”），把这个数存到 m 里。
标记 “沉默” 同学：通过循环，每次从键盘输入一个不能参与展示的同学的编号 x，然后把这个同学对应的小牌子（d）翻成 1，表示他不能参与展示。
6. 喊出能展示的同学编号
for (int i = t[0].r; i; i = t[i].r) {if (t[i].d == 0) {printf("%d ", i);}}return 0;
} 从 “虚拟同学” 右边的第一个同学开始，一个一个往后看。如果这个同学的小牌子（d）是 0，说明他能参与展示，就把这个同学的编号通过 printf 喊出来，后面再跟个空格。最后程序结束。
总结：整个程序就是通过模拟同学排队、新同学加入和部分同学 “沉默” 的过程，最后输出能参与展示的同学编号，利用结构体数组和链表的思想实现了队伍的管理。
题目二：
AC代码 ：
#include <stdio.h>#define N 1000001int f[N], n, m, x, y;// 并查集(路径压缩)
int r(int x) {if (x != f[x]) {f[x] = r(f[x]); }return f[x];
}// 合并
void u(int x, int y) {int r1 = r(x); int r2 = r(y); f[r1] = r2;
}int main() {while (1) {int a = 0;scanf("%d", &n);if (n == 0) {break;}scanf("%d", &m);for (int i = 1; i <= n; i++) {f[i] = i;}for (int i = 1; i <= m; i++) {scanf("%d %d", &x, &y);u(x, y);}for (int i = 1; i <= n; i++) {if (r(i) == i) {a++;}}printf("%d\n", a - 1);}return 0;
}
题解：
1.#define N 1000001：定义一个宏 N，表示数组的最大长度，用于存储并查集的数据。
2.全局变量定义
int f[N], n, m, x, y;f[N]：并查集的核心数组，f[i] 表示节点 i 的父节点。初始时，每个节点的父节点是它自己。
n：表示图中节点的数量。
m：表示图中边的数量。
x 和 y：用于临时存储输入的每条边的两个端点。
3. 查找函数 r
// 并查集(路径压缩)
int r(int x) {if (x != f[x]) {f[x] = r(f[x]); }return f[x];
} 这个函数的作用是查找节点 x 所在集合的根节点（也就是祖先节点）。
if (x != f[x])：如果 x 不是根节点（即 x 的父节点不是它自己），就递归地查找 x 的父节点的根节点，并将 x 的父节点直接设为根节点，这就是路径压缩的过程，目的是为了让后续查找操作更快。
最后返回根节点。
4. 合并函数 u
// 合并
void u(int x, int y) {int r1 = r(x); int r2 = r(y); f[r1] = r2;
} 这个函数的作用是将节点 x 和节点 y 所在的集合合并成一个集合。
首先分别调用 r(x) 和 r(y) 找到 x 和 y 所在集合的根节点 r1 和 r2。
然后将 r1 的父节点设为 r2，这样两个集合就合并成一个集合了。
5. 主函数 main
int main() {while (1) {int a = 0;scanf("%d", &n);if (n == 0) {break;}scanf("%d", &m);for (int i = 1; i <= n; i++) {f[i] = i;}for (int i = 1; i <= m; i++) {scanf("%d %d", &x, &y);u(x, y);}for (int i = 1; i <= n; i++) {if (r(i) == i) {a++;}}printf("%d\n", a - 1);}return 0;
} while (1)：这是一个无限循环，不断读取输入数据，直到输入的节点数量 n 为 0 时退出循环。
int a = 0：用于统计图中连通分量的数量。
scanf("%d", &n) 和 scanf("%d", &m)：分别读取节点数量和边的数量。
for (int i = 1; i <= n; i++) { f[i] = i; }：初始化并查集，将每个节点的父节点设为它自己，表示每个节点最初都属于一个单独的集合。
for (int i = 1; i <= m; i++) { scanf("%d %d", &x, &y); u(x, y); }：循环读取每条边的两个端点 x 和 y，并调用 u(x, y) 函数将它们所在的集合合并。
for (int i = 1; i <= n; i++) { if (r(i) == i) { a++; } }：遍历所有节点，统计根节点的数量，也就是连通分量的数量。因为根节点的特点是它的父节点就是它自己，所以当 r(i) == i 时，说明节点 i 是一个根节点。
printf("%d\n", a - 1);：输出将这些连通分量连接成一个连通图所需添加的最少边数。根据图论知识，要将 a 个连通分量连接成一个连通图，最少需要添加 a - 1 条边。
