题解(关系并查集模板) 2018寒假训练1 E.谁在说谎

问题 E: 谁在说谎 时间限制: 1 Sec 内存限制: 128 MB [提交][状态][讨论版] 题目描述 有n个小朋友，编号1到n，老师将他们分成两队，但分完后小朋友又乱跑了，不知道谁分在哪队，于是他求助很多小机器人，编号1到m，这些机器人会按顺序提示一些信息。 提示的信息是这样的： a b， 表示小朋友a和小朋友b不在同一队。 但是这些机器人偶尔会撒谎，老师就来请求你帮忙，看看哪个机器人最先撒谎。撒谎的规则是这样的，只要当前机器人说的信息与之前所有信息不冲突，就不算撒谎，如果冲突了，就算撒谎了。 输入 输入n，m 然后输入m行，第i行为机器人i提供的信息 输出 如果没机器人撒谎，输出”OK” 否则输出第一个撒谎机器人的编号 样例输入 3 3 1 2 2 3 1 3 样例输出 3 提示 【样例说明】 前两个机器人说的没冲突，得出1和3应该在同一队，所以第三个机器人撒谎了 【数据规模和约定】 1<=n<=5000 1<=m<=100000 题解 ```cpp //我不知道 #include <stdio.h> bool flag; int n, m, findx, findy, x, y; int fa[10005]; int find(int x) { if (fa[x] != x) fa[x] = find(fa[x]); return fa[x]; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n + n; i++) fa[i] = i; flag = true; for (int i = 1; i <= m; i++) { scanf("%d%d", &x, &y); findx = find(x); findy = find(y); if (findx != findy) { fa[findx] = find(y + n); fa[findy] = find(x + n); } else { flag = false; printf("%d\n", i); break; } } if (flag) printf("OK\n"); return 0; } ```