poj 1182 http://poj.org/problem?id=1182
分析：这个题大意说的非常清楚了，就是求出假话的个数，题目中给的假话要求有三个
① 当前的话与前面的某些真的话冲突，是假话；
②当前的话中X或Y比N大，是假话；
③当前的话表示X吃X，是假话。
②和③很好判断了，最难的就是假话条件①啦！！ 题中说有三种动物A,B,C； A-->B-->C-->A(A吃B， B吃C，C又吃A)， 形成一个环； 然而我们又没办法把所给的动物（数字代替）确切的分给哪一类。 那么就不分了，既然这三种动物构成一个环么，那么我们就将所有相关联的元素合并成一个集合。 集合中有一个代表元素（下面也可能叫根元素）。 通过元素与根元素的关系 来区别他们。 relation[i] = 0 表示与根元素同类relation[i] = 1 表示吃根元素的那类， relation[i] = 2 表示被根元素吃的一类。 通过元素与根元素的关系清晰的将他们分为三类，又不用确切表明哪一类。
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std; int n, m, d, x, y, fx, fy, sum, pre[], relation[];
//初始化集合
void init()
{
for(int i = ; i <= n; i++)
{
pre[i] = i;
relation[i] = ;
}
}
int find(int a)//寻找最终代表元素
{
int i, j;
i = a;
if(pre[a] == a)
return a;
else
{
j = pre[i];
pre[i] = find(j);//通过递归方式
relation[i] = (relation[i] + relation[j]) % ;
//这个地方关键。 边寻找根元素， 边得出和根元素的关系。 这通过
//该元素和父亲元素的关系 还有 父亲元素和根元素的关系 求出。
//这个关系式我是枚举后 总结的 下面有推出的过程。
}
return pre[a];
}
//在这我写了两个合并的函数Union1，Union2，主要是因为d = 1时和 d = 2时
//求relation的方程不同，这个方程在下面也有推到过程
void Union1(int a, int b)
{
pre[fx] = fy;
relation[fx] = ( + (relation[b] - relation[a])) % ;
}
void Union2(int a, int b)
{
pre[fx] = fy;
relation[fx] = ( + (relation[b] - relation[a]) + ) % ;
} int main()
{
scanf("%d%d", &n, &m);
init();
sum = ;
for(int i = ; i <= m; i++)
{
scanf("%d%d%d", &d, &x, &y);
if(x > n || y > n || (d == && x == y))
{
sum++;
continue;
}
fx = find(x);
fy = find(y);
//若x和y的根元素不同，就代表至少其中一个元素不再集合里，需要合并元素
if(fx != fy)
{
if(d == )
Union1(x, y);
else
Union2(x, y);
}
//当x和y的根元素相同时，就代表他们都是集合里的啦！ 这使得工作就关键啦！！
//需要判断这是给的关系和原本存在的关系是否冲突， 如果冲突， 假话就得多一个咯！
else if(fx == fy)
{
if(d == )
{
if(relation[x] != relation[y])
sum++;
}
if(d == )
{
if(relation[x] != (relation[y]+) % )
sum++;
}
}
}
printf("%d\n", sum);
return ;
}
Union2 relation[fx] = (3 + (relation[b] - relation[a]) + 1) % 3;
| x与根元素fx的关系 | y与根元素fy的关系 | fx与fy的关系 | relation[b] - relation[a] |
| 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | -1 |
| 2 | 0 | 2 | -2 |
| 0 | 1 | 2 | 1 |
| 1 | 1 | 1 | 0 |
| 2 | 1 | 0 | -1 |
| 0 | 2 | 0 | 2 |
| 1 | 2 | 2 | 1 |
| 2 | 2 | 1 | 0 |
Union1 relation[fx] = (3 + (relation[b] - relation[a])) % 3;
| x与根元素fx的关系 | y与根元素fy的关系 | fx与fy的关系 | relation[b] - relation[a] |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 0 | 2 | 2 | 2 |
| 1 | 0 | 2 | -1 |
| 1 | 1 | 0 | 0 |
| 1 | 2 | 1 | 1 |
| 2 | 0 | 1 | -2 |
| 2 | 1 | 2 | -1 |
| 2 | 2 | 0 | 0 |
find relation[i] = (relation[i] + relation[j]) % 3;
| i元素与父亲元素j的关系 | j元素与根元素的关系 | i元素与根元素的关系 |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 2 | 2 |
| 1 | 0 | 1 |
| 1 | 1 | 2 |
| 1 | 2 | 0 |
| 2 | 0 | 2 |
| 2 | 1 | 0 |
| 2 | 2 | 1 |
poj2492 和这个题类似 ， 他只是将A，B，C三类动物 变成 男，女两种类。relation可能是同类或异类。如果出现一对是同类那么说明 有异常。 relation关系式： find寻找时relation[i] = (relation[i] + relation[j]) % 2; 合并时relation[fx] = (relation[a] + relation[b] + 1) % 2。
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std; int n, m, x, y, flag, pre[], relation[];
void init()
{
for(int i = ; i <= n; i++)
{
pre[i] = ;
relation[i] = ;
}
}
int find(int a)
{
int r, i, j;
r = a; i = a;
if(pre[a] == a)
return a;
else
{
j = pre[i];
pre[i] = find(j);
relation[i] = (relation[i] + relation[j]) % ;
}
return pre[a];
}
void Union(int a, int b)
{
int fx = find(a);
int fy = find(b);
if(fx != fy)
pre[fx] = fy;
relation[fx] = (relation[a] + relation[b] + ) % ;
}
int main()
{
int t, num; cin >> t;
num = ;
while(num < t)
{
scanf("%d%d", &n, &m);
init();
flag = ;
for(int i = ; i <= m; i++)
{
scanf("%d%d", &x, &y);
if(flag == )continue;
int fx = find(x);
int fy = find(y);
if(fx != fy)
Union(x, y);
else if(fx == fy)
{
if(relation[x] == relation[y])
{
flag = ;
printf("rela%d == rela%d\n", x, y);
}
}
}
printf("Scenario #%d:\n", ++num);
if(flag == )
printf("Suspicious bugs found!\n\n");
else if(flag == )
printf("No suspicious bugs found!\n\n");
}
return ;
}