网址：https://ac.nowcoder.com/acm/contest/3888/G

题目描述

Farmer John has N (1 <= N <= 50,000) pastures, conveniently numbered 1...N,
connected by M (1 <= M <= 100,000) bidirectional paths. Path i connects
pasture A_i (1 <= A_i <= N) to pasture B_i (1 <= B_i <= N) with A_i != B_i.
It is possible for two paths to connect between the same pair of pastures.
Bessie has decided to decorate the pastures for FJ's birthday. She wants to
put a large sign in each pasture containing either the letter 'F' or 'J',
but in order not to confuse FJ, she wants to be sure that two pastures are
decorated by different letters if they are connected by a path.

The sign company insists on charging Bessie more money for an 'F' sign than
a 'J' sign, so Bessie wants to maximize the number of 'J' signs that she
uses. Please determine this number, or output -1 if there is no valid way
to arrange the signs.

输入描述:

  • Line 1: Two integers N and M.
  • Lines 2..M+1: Two integers, A_i and B_i indicating that there is a
    bidirectional path from A_i to B_i.

    输出描述:

  • Line 1: A single integer indicating the maximum number of 'J' signs
    that Bessie can use. If there is no valid solution for
    arranging the signs, output -1.

    输入

    4 4
    1 2
    2 3
    3 4
    4 1

    输出

    2

    题解：

    这道题可以使用拆点并查集。在这里n个牧场可能会分为许多集合，而最后的结果就是将每个集合中相对的两方，将数目最多的一方加入到sum（最终结果）中。
    注意判断-1的情况也是比较容易的，只要输入的x y，的祖先相同，便是-1，即为不可能。

    AC代码：

    #include<iostream>
using namespace std;
const int N=50005;
int n,m;
int a[N*2];//并查集的标志数组 
int s[N]={0};
int pl[N]={0};
void Init(){
  for(int i=1;i<=2*n;i++) a[i]=i;
}
int Find(int x){
  if(x==a[x]) return x;
  return a[x]=Find(a[x]);
}
 void Merge(int x,int y){
  int fx=Find(x),fy=Find(y);
  a[fy]=fx;
 }
 int main(){
  cin>>n>>m;
  Init();
  int x,y;
  while(m--){
      cin>>x>>y;
      if(Find(x)==Find(y)){
          cout<<"-1";
          return 0;
      }
      Merge(x,y+n);
      Merge(y,x+n);
  }
  int b[N*2];
  for(int i=1;i<=2*n;i++) Find(i);//确保每个元素直接与根祖先相连 
  for(int i=1;i<=n;i++){
      s[a[i]]++;//记录与a[i]祖先相同的农场的数量 
      //数组b是为了标识是否有农场没有与其他农场相连
      //之前以s[i]==1标识，是错误的，因为5 1
      //                                 1 2
      //这样最后的结果是5,因为此时s[1]==1,所以判断是否与其他农场相连
      //应当从i到2*n进行查找 
      b[a[i]]++; 
      b[a[i+n]]++;
  }
  int sum=0;
  for(int i=1;i<=n;i++){
      if(b[i]==1){//没有与其他农场相连，直接加一 
          sum++;
          continue;
      }
      if(s[i]==0||pl[i]) continue;//当s[i]==0,说明i不是祖先，!pl[i]说明i已经被遍历过了 
      sum+=max(s[i],s[a[i+n]]);//找到同一个并查集中相对的两方最多的一方 
      pl[a[i+n]]=1; 
      pl[i]=1;
  }
  cout<<sum<<endl;
  return 0;
 }

打卡第七天，这道题我的想法着实非常容易，为自己感到骄傲！！！