一个并查集的应用,不是把同一类动物并成一类,而是把能够判断其关系的并成一类,其中每个节点都维护一个relat域,表示其和代表元的关系,0表示同一类,1表示其以代表元为食,2表示其被代表元吃,合并时维护该域即可,对于给出的一个句话,先判断这俩个元素是否已经合成一个集合,如果在一个集合中就可以知道它们之前描述的关系了,判断是否与之前描述的关系相辅即可, 如果不在一个集合中,就把这句话当成真的,然后按照其关系合并这俩个集合即可,最后这题不要读入到文件尾,估计数据文件中有其他信息
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <cstring> #include <stack> #include <cctype> #include <utility> #include <map> #include <string> #include <climits> #include <set> #include <string> #include <sstream> #include <utility> #include <ctime> //#pragma comment(linker, "/STACK:1024000000,1024000000") using std::priority_queue; using std::vector; using std::swap; using std::stack; using std::sort; using std::max; using std::min; using std::pair; using std::map; using std::string; using std::cin; using std::cout; using std::set; using std::queue; using std::string; using std::istringstream; using std::getline; using std::make_pair; using std::greater; //关系: relat[x] = 0表示层 x与fa[x]是同一类 // = 1表示x吃fa[x] // = 2表示x被fa[x]吃 const int MAXN(50010); int fa[MAXN], relat[MAXN]; void init(int n) { for(int i = 1; i <= n; ++i) { fa[i] = i; relat[i] = 0; } } int find(int sour) { if(sour == fa[sour]) return sour; int temp = find(fa[sour]); relat[sour] = (relat[sour]+relat[fa[sour]])%3; fa[sour] = temp; return temp; } int change[3] = {0, 2, 1}; void Union(int sour1, int sour2, int flag) //flag = 0 表示是同一类 = 1表示 sour1吃sour2 { int fs1, fs2; fs1 = find(sour1); fs2 = find(sour2); if(fs1 != fs2) { relat[fs1] = (change[relat[sour1]]+relat[sour2]+flag)%3; fa[fs1] = fs2; } } bool is_legal(int sour1, int sour2, int flag) //flag = 0表示 sour1 与sour2是同一类, =1 表示sour1吃sour2 { int fs1, fs2; fs1 = find(sour1); fs2 = find(sour2); if(fs1 != fs2) return true; if(flag == 0) return relat[sour1] == relat[sour2]; if((relat[sour1] == 1 && relat[sour2] == 0) ||(relat[sour1] == 2 && relat[sour2] == 1) ||(relat[sour1] == 0 && relat[sour2] == 2)) return true; return false; } int main() { int N, K; int flag, op1, op2; scanf("%d%d", &N, &K); init(N); int ans = 0; for(int i = 1; i <= K; ++i) { scanf("%d%d%d", &flag, &op1, &op2); --flag; if(op1 > N || op2 > N) ++ans; else { if(is_legal(op1, op2, flag)) Union(op1, op2, flag); else ++ans; } } printf("%d\n", ans); return 0; }