第 32届全国信息学奥林匹克竞赛 第一试 程序自动分析 第 2页 共 10页 程序自动分析 【问题描述】 在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满 足。 考虑一个约束满足问题的简化版本：假设 𝑥1, 𝑥2, 𝑥3, ⋯ 代表程序中出现的变 量，给定 𝑛 个形如 𝑥𝑖 = 𝑥𝑗 或 𝑥𝑖 ≠ 𝑥𝑗 的变量相等/不等的约束条件，请判定是否 可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如， 一个问题中的约束条件为： 𝑥1 = 𝑥2, 𝑥2 = 𝑥3, 𝑥3 = 𝑥4, 𝑥1 ≠ 𝑥4 ，这些约束条件显 然是不可能同时被满足的，因此这个问题应判定为不可被满足。 现在给出一些约束满足问题，请分别对它们进行判定。 【输入格式】 从文件 prog.in中读入数据。 输入文件的第 1 行包含 1 个正整数 𝑡 ，表示需要判定的问题个数。注意这些 问题之间是相互独立的。 对于每个问题，包含若干行： 第 1 行包含 1 个正整数 𝑛 ，表示该问题中需要被满足的约束条件个数。 接下来 𝑛 行，每行包括 3 个整数 𝑖, 𝑗, 𝑒 ，描述 1 个相等/不等的约束条件，相 邻整数之间用单个空格隔开。若 𝑒 = 1 ，则该约束条件为 𝑥𝑖 = 𝑥𝑗 ；若 𝑒 = 0 ， 则该约束条件为 𝑥𝑖 ≠ 𝑥𝑗 ； 【输出格式】 输出到文件 prog.out中。 输出文件包括 𝑡 行。 输出文件的第 𝑘 行输出一个字符串“YES”或者“NO”（不包含引号，字母 全部大写），“YES”表示输入中的第 𝑘 个问题判定为可以被满足，“NO”表示不 可被满足。 【样例输入 1】 2 2 1 2 1 1 2 0 2 1 2 1 2 1 1 第 32届全国信息学奥林匹克竞赛 第一试 程序自动分析 第 3页 共 10页 【样例输出 1】 NO YES 【样例说明 1】 在第一个问题中，约束条件为： 𝑥1 = 𝑥2, 𝑥1 ≠ 𝑥2 。这两个约束条件互相矛 盾，因此不可被同时满足。 在第二个问题中，约束条件为： 𝑥1 = 𝑥2, 𝑥2 = 𝑥1 。这两个约束条件是等价 的，可以被同时满足。 【样例输入 2】 2 3 1 2 1 2 3 1 3 1 1 4 1 2 1 2 3 1 3 4 1 1 4 0 【样例输出 2】 YES NO 【样例说明 2】 在第一个问题中，约束条件有三个： 𝑥1 = 𝑥2, 𝑥2 = 𝑥3, 𝑥3 = 𝑥1 。只需赋值使 得 𝑥1 = 𝑥2 = 𝑥3 ，即可同时满足所有的约束条件。 在第二个问题中，约束条件有四个： 𝑥1 = 𝑥2, 𝑥2 = 𝑥3, 𝑥3 = 𝑥4, 𝑥1 ≠ 𝑥4 。由 前三个约束条件可以推出 𝑥1 = 𝑥2 = 𝑥3 = 𝑥4 ，然而最后一个约束条件却要求 𝑥1 ≠ 𝑥4 ，因此不可被满足。 【样例输入输出 3】 见选手目录下的 prog/prog.in与 prog/prog.ans。 第 32届全国信息学奥林匹克竞赛 第一试 程序自动分析 第 4页 共 10页 【数据规模与约定】 所有测试数据的范围和特点如下表所示 测试点编号 𝑛 的规模 𝑖, 𝑗 的规模 约定 1 1 ≤ 𝑛 ≤ 10 1 ≤ 𝑖, 𝑗 ≤ 10,000 1 ≤ 𝑡 ≤ 10 𝑒 ∈ {0,1} 2 3 1 ≤ 𝑛 ≤ 100 4 5 1 ≤ 𝑛 ≤ 100,000 6 7 8 1 ≤ 𝑛 ≤ 100,000 1 ≤ 𝑖, 𝑗 ≤ 1,000,000,000 9 10