题目来源:http://acm.nyist.cf/problem/1577
此外: http://poj.org/problem?id=1182
题目描述:
有一个大型工厂,其中中枢控制系统出了问题,它的中枢控制系统是由N个纽带连接而成
只有三种类型的纽带,纽带以1-N编号。
每一种中枢纽带都对应着一种前驱纽带和一种后继纽带,后继纽带的后继就是当前中枢的前驱纽带。
由于该中枢十分的重要,每个纽带都对应这一个负责人。
只有对应的负责人知道自己负责的纽带与其他纽带之间的关系,
但是也只知道自己负责的那个纽带的后继关系和与同种的各个纽带,没有谁会知道前驱关系。
问题就出在纽带的连接顺序上,于是修理人员将中枢的纽带都取了出来,并把所有负责人都叫了过来。
但是其中有些负责人是破坏分子,不会说出他对应的纽带的真实消息。
每个负责人只有两种描述方法:
第一种说法是“X S Y”,表示X和Y纽带是同种纽带无法连接;
都二种说法是“X C Y”,表示X纽带的后继是Y。
当前的话与前面的某些真的话冲突,就是假话
当前的话中 X 或 Y 比 N 大,就是假话
当前的话表示 X的后继是X,就是假话
若由N(1 <= N <= 50,000)个负责人,负责人总共说了K(0 <= K <= 100,000)句话,你的任务是输出假话的总数,帮助修理人员尽早完工。
输入描述:
第一行是两个整数N和K,以一个空格分隔。 以下K行每行是三个变量整数X,字符T,整数Y,两数之间用一个空格隔开,其中T表示说法的种类。 若T='S',则表示X和Y是同种类型。 若T='C',则表示X的后继是Y。
输出描述:
只有一个整数,表示假话的数目。
样例输入:
复制
50 7 54 S 1 1 C 2 2 C 3 3 C 3 1 S 3 3 C 1 5 C 5
样例输出:
4
提示:
来源:
上传者:hclg
思路:https://blog.csdn.net/nuoyanli/article/details/86553219 上图最好了
参考代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<cmath>
#include<queue>
const double pi = acos(-1);
using namespace std;
#define N 50010
int pre[N],re[N];
void init(int n)
{
for(int x = 1; x <= n; x++)
{
pre[x] = x;
re[x] = 0;
}
}
int Find(int x)
{
if(x == pre[x])
return x;
int t = pre[x];
pre[x] = Find(pre[x]);
re[x] = (re[x]+re[t])%3;
return pre[x];
}
void Join(int x, int y, int z)
{
int fx = Find(x);
int fy = Find(y);
pre[fy] = fx;
re[fy] = (re[x]-re[y]+3+(z-1))%3;
}
int main()
{
int n, m,ans = 0,x, y,z;
scanf("%d%d", &n, &m);
init(n);
while(m--)
{
char c;
scanf("%d %c %d", &x, &c, &y);
if(c=='S')
z=1;
else
z=2;
if(x > n || y > n || (z == 2 && x == y))
ans++;
else if(Find(x) == Find(y))
{
if(z == 1 && re[x] != re[y]) ans++;
if(z == 2 && (re[x]+1)%3 != re[y]) ans++;
}
else Join(x, y, z);
}
printf("%d\n", ans);
return 0;
}