E. Split into two sets

Codeforces Round #805 (Div. 3)

Problem

give n A domino , Each domino has two numbers . Ask if you can divide all dominoes into two sets , So that there are no duplicate numbers in each set .

Solution

Bipartite graph ：

Definition ： Nodes consist of two sets , And there are no edges in two sets .
nature ：

1. If the dots in two sets are dyed red and blue respectively , It can be found that every edge in the bipartite graph must be connected with a red dot and a blue dot
2. There is no ring with odd length in bipartite graph （ Only walk an even number of times can you return to a set ）

Type and search ( Extended domain )

Extended domain can be referred to 《 The food chain 》 This kind of problem . Portal

1. Generally, the maintenance of joint search sets is only connectivity and transitivity （ A friend's friend is a friend ）
   Categories and search sets are used to maintain , The enemy of the enemy is a friend .

2. Suppose you want to maintain a union search set with only four elements (n = 4)：

   1. Double the array ：1-4 What we maintain is the relationship of friends ,5-8 Maintain a hostile relationship
      
   2. If 1,2 It's the enemy , be ：
      merge(1, 2 + n), merge(2, 1 + n);
      If 2, 4 It's the enemy , be ：
      merge(2, 4 + n), merge(4, 2 + n);
   3. Looking at the picture above, we can see ：1 and 4 adopt 2 + n This point is connected , Form a friendship

Code

const int N = 4e5 + 5, M = 1e6 + 7;
int f[N], a[N];
int fd(int x)
{
    
	if (x == f[x]) return x;
	return f[x] = fd(f[x]);
}

void merge(int x, int y)
{
    
	int fx = fd(x), fy = fd(y);
	if (fx != fy) f[fx] = fy;
}

int main()
{
    
	IOS;
	int T; cin >> T;
	while (T--)
	{
    
		int n; cin >> n;
		for (int i = 1; i <= n * 2; i++) f[i] = i, a[i] = 0;

		int flag = 1;
		for (int i = 1, x, y; i <= n; i++)
		{
    
			cin >> x >> y;
			a[x]++; a[y]++;
			if (x == y) flag = 0;

			if (fd(x) == fd(y)) flag = 0;
			else
			{
    
				int dx = x + n, dy = y + n;
				merge(x, dy);
				merge(dx, y);
			}
		}

		for (int i = 1; i <= n && flag; i++)
			if (a[i] != 2) flag = 0;

		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}


	return 0;
}