zoj 1518This Sentence is False

题目链接：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827365017

题目考察：并查集+dfs

难度评价：中等

解题报告：

题目在poj中也可以找到poj1291

当然，我感觉这道题和poj的食物链也有点相似，可以说是食物链的plus版，还不错

与i对立的情况必定是包含在除了i的情况中，所以没有必要进行统计。
在遍历num数组的过程中，取num[find_set(i)]和num[find_set(i+n)]中较大的一组。
即：取i或者～i。因为不存在悖论，所以i和～i必定有一个成立。
我们可以考虑这样一种方式：对于和i对立的case来说，这个情况肯定是i的子集，也就是说*i属于i，包含其中所以说可以省去统计的必要

那么在遍历num过程中，我们可以取max(num[find_set(i)],num[find_set(i+n)）

那问题就解决了；

当然，这道题也有点像刚做的1703Find them, Catch them

也就是说用hash也可以

题目思路广，用好一种就可以了

 1 #include <iostream> 2 #include <fstream> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 const int maxn = 1000+5; 7 int n; 8 int set[2*maxn],vis[maxn*2],num[maxn*2]; 9 void init(int a)10 {11     for(int i = 1;i <= a;i++) set[i] = i;12 }13 int find_set(int a)14 {15     return a == set[a] ? a : set[a] = find_set(set[a]);16 }17 void union_set(int a,int b)18 {19     a = find_set(a);20     b = find_set(b);21     if(a != b)22         set[a] = b;23 }24 void solve()25 {26     int ans = 0;27     memset(vis,0,sizeof(vis));28     memset(num,0,sizeof(num));29     for(int i = 1;i <= n;i++)30         num[find_set(i)]++;31     for(int i = 1;i <= n;i++)32     {33         if(vis[find_set(i)] || vis[find_set(i+n)])34             continue;35         ans += max(num[find_set(i)],num[find_set(i+n)]);36         vis[find_set(i)] = vis[find_set(i+n)] = 1;37     }38     printf("%d\n",ans);39 }40 int main()41 {42     while(scanf("%d",&n)&&n)43     {44         char str[20];45         int x;46         init(n*2);47         bool flag = false;48         for(int i = 1;i <= n;i++)49         {50             scanf("%s%d%s%s",str,&x,str,str);51             if(flag) continue;52             if(str[0] == 't')53             {54                 55                 if(find_set(x+n) == find_set(i) || find_set(x) == find_set(i+n))56                     flag = 1;57                 else58                 {59                     union_set(i,x);60                     union_set(i+n,x+n);61                 }62             }63             else64             {65                 if(find_set(x) == find_set(i) || find_set(x+n) == find_set(i+n))66                     flag = 1;67                 else68                 {69                     union_set(i+n,x);70                     union_set(i,x+n);71                 }72             }73         }74         if(flag) printf("Inconsistent\n");75         else solve();76     }77     return 0;78 }