[USACO | UPC] Liars and Truth Tellers | 拓展域并查集

网址链接或者是链接

题目描述

After spending so much time around his cows, Farmer John has started to  understand their language. Moreover, he notices that among his N cows (2 ≤ N ≤ 1000 ), some always tell the truth while others always lie.

FJ carefully listens to M statements (1 <= M <= 10,000) from his cows, each of the form “x y T”, meaning that “cow x claims cow y always tells the truth” or “x y L”, meaning that “cow x claims cow y always tells lies”.

Each statement involves a pair of different cows, and the same pair of cows may appear in multiple statements.

Unfortunately, FJ believes he might have written down some entries in his list incorrectly, so there may not be a valid way to designate each cow as a truth teller or a liar that is consistent with all the M statements on FJ’s list. To help FJ salvage as much of his list as possible, please compute the largest value of A such that there exists a valid way to designate each cow as a truth teller or a liar in a manner that is consistent with the first A entries in FJ’s list.

输入

• Line 1: Two space-separated integers, N and M.
• Lines 2…1+M: Each line is of the form “x y L” or “x y T”, describing a statement made by cow x about cow y.

输出

• Line 1: The maximum value of A such that the first A entries in FJ’s list can be consistent with some assignment of “truth teller” or “liar” to the N cows.

样例输入

4 3
1 4 L
2 3 T
4 1 T

样例输出

2

提示

There are 4 cows and 3 statements. Cow 1 says that cow 4 lies, cow 2 says that cow 3 tells the truth, and cow 4 says that cow 1 tells the truth.Statements 1 and 3 cannot both be satisfied at the same time, but

statements 1 and 2 can be, if we let cows 1…3 tell the truth and cow 4 be a liar.

在思考这个题的时候，想到过之前做过的一道类似的题目，当时也做了总结：链接，这一类叫做拓展域 并查集

对于这个题目：

首先我们可以知道，每个点都有两个属性，真或者是假

对于a b L的情况，我们可以知道{

这句话表达的意思是a说b假

结果会有两种，a真b假或者是a假b真

}

对于a b T的情况，我们可以知道{

这句话表达的意思是a说b真

结果会有两种，a真b真，a假b假

}

所以说这里我们就可以用并查集来维护每个点的真假，如果说同一个点出现了两个真假状态，那就是矛盾的情况

int n,m;
int fa[maxn];
void init() {
  for(int i=1; i<=2*n; i++) fa[i] = i;
}
int find(int x) {
  if(x == fa[x]) return x;
  else return fa[x] = find(fa[x]);
}
int main() {
  n = read,m = read;
  init();
  int x,y;
  char c;
  int flag = 1,ans = 0,pos = 0;
  for(int i=1; i<=m; i++) {
    scanf("%d %d %c",&x,&y,&c);
    if(c == 'L') {
      fa[find(n + x)] = find(y);
      fa[find(n + y)] = find(x);
    } else {
      fa[find(x)] = find(y);
      fa[find(n + x)] = find(n + y);
    }
    if(find(y) == find(n + y)) {
      flag = 0;
      pos = i-1;
    }
    if(flag) ans ++;
  }
//  assert(pos == flag);
  cout << ans << endl;
  return 0;
}