用拓展域并查集！！！

#include<bits/stdc++.h>
using namespace std;
int fa[21000];//fa[1]到fa[n]为真话奶牛域，fa[n+1]到fa[2n]为假话奶牛域 
int find(int x){return (fa[x]==x)?x:(fa[x]=find(fa[x]));}//找根节点 
void he(int x,int y){fa[find(x)]=find(y);}//合并 
int main()
{
	int n,m;cin>>n>>m;
	for(int i=1;i<=2*n;i++)fa[i]=i;
	for(int i=1,x,y;i<=m;i++)
	{
		char c;cin>>x>>y>>c;
		if(c=='T')he(x,y),he(x+n,y+n);//若x说真话则x,y均为真话奶牛，反之都为假话奶牛， 
		else he(x,y+n),he(x+n,y);//他俩一定有一个是真话奶牛，一个是假话奶牛
		if(find(x)==find(x+n))return cout<<i-1,0;
	}
	cout<<m;
}

题解

#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;
}

#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;
}