Description

【题意】
约翰有 $N$ 头奶牛，有一部分奶牛是真话奶牛，它们只说真话，而剩下的是假话奶牛，只说假话。
有一天，约翰从奶牛的闲谈中陆续得到了 $M$ 句话，第i句话出自第 $X_i$ 头奶牛，它会告诉约翰第 $Y_i$ 头是一头真话奶牛还是假话奶牛。
然而，约翰记性不好，他可能把这些话的内容记错了。
请检查一下约翰的记录是否会有矛盾，帮助他找到一个尽量大的 $K$ ，使得约翰记下的前 $K$ 句话不矛盾。

【输入格式】
• 第一行：两个整数 $N$ 和 $M$，$1 \le N \le 1000,1 \le M \le 10000$
• 第二行到 $M+1$ 行：第 $i+1$ 行有两个整数：$X_i$ 和 $Y_i$ ，$1 \le X_i,Y_i \le N$，接下来有一个字符：
– 如果是$T$，表示 $X_i$ 说 $Y_i$ 是真话奶牛；
– 如果是$L$，表示 $X_i$ 说 $Y_i$ 是假话奶牛；

【输出格式】
• 单个整数，即表示题目描述中的 $K$

【样例输入】
4 3
1 4 L
2 3 T
4 1 T

【样例输出】
2

【解释】
前两句没有矛盾,但第一句和第三句存在矛盾

Hint

#include<bits/stdc++.h>
using namespace std;
int fa[21000];
int findfa(int x){return (fa[x]==x)? x : (fa[x]=findfa(fa[x]));}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=2*n;i++)fa[i]=i;
    bool bk=1;
    int ans=0;
    for(int i=1,x,y;i<=m;i++)
    {
        char ss[5];scanf("%d%d%s",&x,&y,ss);
        if(ss[0]=='T')
        {
            fa[findfa(x)]=findfa(y);
            fa[findfa(x+n)]=findfa(y+n);
        }
        else
        {
            fa[findfa(x)]=findfa(y+n);
            fa[findfa(x+n)]=findfa(y);
        }
        if(findfa(y)==findfa(n+y)) bk=False;
        if(bk)ans++;
    }
    printf("%d",ans);
    return 0;
}

Source

J4