题目来源: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;
}