洛谷P1892.团伙

​​传送门​​​ 题目描述

给定 n个人，他们之间有两个种关系，朋友与敌对。可以肯定的是：

与我的朋友是朋友的人是我的朋友

与我敌对的人有敌对关系的人是我的朋友

现在这 n个人进行组团，两个人在一个团队内当且仅当他们是朋友。

求最多的团体数。

输入格式

第一行一个整数 n代表人数。

第二行一个整数 m 代表每个人之间的关系。

接下来 mm 行每行一个字符 opt 与两个整数 p,q

思路：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int mod = 1e9 + 7;
int a[1010];
int pre[1010];
int enemy[1010];
int find(int x)
{
  if(pre[x] != x)
  return pre[x] = find(pre[x]);
  return pre[x];
}

int main()
{
  
  int s,m;
  scanf("%d%d",&s,&m);
  for(int i = 1; i <= s*2; i++)
  {
    pre[i] = i;
    enemy[i] = i;
  }
  char c;
  for(int i = 0; i <m; i++)
  {
    
    scanf(" %c",&c);
    int x,y;
    scanf("%d%d",&x,&y);
    if(c == 'F')
    {
      pre[find(x)] = pre[find(y)];
    }
    else
    {
      pre[find(x+s)] = find(y);
      pre[find(y+s)] = find(x);
    }
  }
  int ans = 0;
  for(int i = 1; i <= s; i++)
  {
    if(pre[i] == i)
    ans++;
  }
  printf("%d\n",ans);
}