Luogu p1892 [boi2003] Gang (and search for variant anti set)

[BOI2003] gangs

Title Description

Now there is $n$ personal , There are two relationships between them ： Friends and enemies . We know ：

• A person's friend's friend is a friend
• A man's enemy is his friend

Now we need to form a group of these people . Two people in a group if and only if they are friends . Ask for the maximum number of possible groups of these people .

Input format

Enter an integer in the first line $n$ Number of Representatives .

On the second line, enter an integer $m$ It means to list $m$ A relationship .

Next $m$ That's ok , One character per line $opt$ And two integers $p,q$, They represent the relationship （ Friends or enemies ）, The first and second of the two people involved . among $opt$ There are two possibilities ：

• If $opt$ by F, It means $p$ and $q$ It's a friend. .
• If $opt$ by E, It means $p$ and $q$ It's the enemy .

Output format

One integer per line represents the largest number of groups .

Examples #1

The sample input #1

6
4
E 1 4
F 3 5
F 4 6
E 1 2

Sample output #1

3

Tips

about $100\%$ The data of ,$2\le n\le 1000$,$1\le m\le 5000$,$1\le p,q\le n$.

The question ：

My friend's friend is my friend , My enemy's enemy is my friend , The final output Number of gangs . Be careful , Two people in a group if and only if they are friends .

Ideas ：

It is easy to think of this problem as side weighted and search set , But it's not , According to the original problem surface of this problem , In fact, there can be no relationship between two people ： May have never met , Or the police department doesn't know their relationship . The translation on Luo Gu said that everyone has a relationship .

Experience that can be accumulated in this topic ：

• For the relationship between two people , There can be no relationship , Record relationships that cannot be merged , Merge people who can be merged when you find them again .
• For the relationship between two people , There must be a relationship , use Weighted and search set .

For this question , We introduce a new approach ： Anti set of union search set .

a Express a My friends ,a + n Express a Enemy set of

• If a and b It's a friend. , that take a and b My friends Just connect : p[Find(a)] = Find(b);
• If a and b It's the enemy , be take a The enemy of sets with b My friends Connected to a , take b The enemy of sets with a My friends Connected to a , namely : p[Find(a + n)] = Find(b),p[Find(b + n)] = Find(a)

Finally, count the number of gangs ,1 ~ n in （ Friends collection ） all p[i] == i The number of people is the answer . Because according to the meaning of the title , All gangs must be distributed in the concentration of friends , therefore as long as Count the number of nodes without ancestors in the friend set .

Code ：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
//#define int long long
int n, m;
const int N = 1010;
int p[N << 1];

int Find(int x)
{
    
	if (p[x] != x) p[x] = Find(p[x]);
	return p[x];
}

signed main()
{
    
	int T = 1; //cin >> T;

	while (T--)
	{
    
		cin >> n >> m;
		int res = 0;
		for (int i = 1; i < N<<1; ++i) p[i] = i;
		for (int i = 1; i <= m; ++i)
		{
    
			char op[2]; int a, b;
			cin >> op >> a >> b;
			int pa = Find(a), pb = Find(b);
			int pan = Find(a + n), pbn = Find(b + n);
			if (*op == 'F')
			{
    
				p[pb] = pa;
			}
			else
			{
    
				p[pbn] = pa;
				p[pan] = pb;
			}
		}
		for (int i = 1; i <= n; ++i) if (p[i] == i) ++res;
		cout << res << '\n';
	}

	return 0;
}