E. Split into two sets

Topic link :  Portal

 

  The main idea of the topic : Yes n Set dominoes , Each set of cards has two numbers a,b,(1<=a,b<=n), Ask if you can put this n Group dominoes are divided into two groups , Make the numbers on each group of dominoes different , And all dominoes can be assigned ( That is, the number of all dominoes in a group is 1~n).

Ideas : There are many ways to solve this problem , Here are two , One is to use Type and search do , One is dyeing Bipartite graph Composition

One 、 Type and search

The basic query set maintenance is One Relationship , If a friend's friend is a friend , And category and search set can be maintained Multiple Relationship , If the enemy of the enemy is a friend , There is a more hostile relationship , Generally, it can be achieved by expanding and querying the scale ;

Such as : 1 2 3 4, Four people ,  1,2 2,3 It's a friend. , Then we can know through the joint search set connection 1,3 It's a friend.

If we want to add the enemy relationship , We can Double the size of the search set , Then for 1 2 3 4 1+4 2+4 3+4 4+4

namely The first four 1 2 3 4 Keep friends , The last four 5 6 7 8 For the enemy relationship , So if 1,2 For the sake of hostility , Even 1,2+4 and 1+4, 2 Two sides , To build a hostile relationship , such , When 2,3 When it's a hostile relationship , You will find 1,3 Connected indirectly , That is, the enemy of the enemy is a friend , It completes two kinds of joint search

 

  Then for this problem, we can establish two categories and search the set , A category is a group to carry out and search set construction , For example 5

2 1
1 2
4 3
4 3
5 6
5 7
8 6
7 8

Put one domino into a set at a time , Such as 1,2 Put in collection 1,  1+n, 2+n Then put into the set 2, This appears for the second time 1,2 When You can judge , 1,2 Appear repeatedly in the same set

The code is as follows :

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <iterator>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <unordered_map>
using namespace std;

stringstream ss;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PIII;
const int N = 3e5+10, M = 20, mod = 1e9+7;
const int INF = 0x3f3f3f3f;

int n,q;
int p[2*N]; //  Double the size of search set 

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

void merge(int x,int y)
{
    int px = find(x);
    int py = find(y);
    if(px != py) p[px] = py;
}

void solve()
{
    cin>>n;
    map<int, int> mp; //  Record the number of times 
    for(int i = 1; i<=2*n; i++) p[i] = i;
    int f = 1;
    for(int i = 1; i<=n; i++)
    {
        int a,b;
        cin>>a>>b;
        mp[a]++, mp[b]++;
        if(mp[a]>2 || mp[b]>2) f = 0;
        if(a == b) f = 0;
        int x = a, y = b, dx = a+n, dy = b+n; // x,y In a collection , dx,dy In another set 
        if(find(x) == find(y)) f = 0;
        else
        {
            merge(x, dy);
            merge(y, dx);
        }
    }

    if(f) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//    solve();
    int T;
    cin>>T;
    while(T -- )
    {
        solve();
    }
}

Two 、 Bipartite graph

Think of each domino as a two-way side connection , For example 5

2 1
1 2
4 3
4 3
5 6
5 7
8 6
7 8

The picture completed after the connection is {1,2}-{2,1}, {3,4}-{3,4}, {5,6}-{6,8}-{8,7}-{7,5} Three rings   It is not difficult to find that when the ring is even , We can put it in a set through taking , Such as {5,6}-{6,8}-{8,7}-{7,5}, take {5,6},{8,7} Put it in a set , The other two are placed in another set ( That is to build a bipartite graph ), In this way, there will be no repetition in two sets , And if there are odd rings , There must be repetition when taking cards , So after building the map , Judge whether there is an odd ring .

The code is as follows : 

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <iterator>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <unordered_map>
using namespace std;

stringstream ss;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PIII;
const int N = 3e5+10, M = 20, mod = 1e9+7;
const int INF = 0x3f3f3f3f;

int n,q;
int col[N];
vector<int> v[N];
int ok = 1;

void dfs(int u)
{
    for(auto t : v[u])
    {
        if(!col[t])
        {

            col[t] = -col[u];
            dfs(t);
        }else if(col[t] == col[u]) ok = 0;
    }
}

void solve()
{
    cin>>n;
    map<int, int> mp; //  Record the number of times 
    for(int i = 1; i<=n; i++) v[i].clear(), col[i] = 0;
    int f = 1;
    for(int i = 1; i<=n; i++)
    {
        int a,b;
        cin>>a>>b;
        mp[a]++, mp[b]++;
        if(mp[a]>2 || mp[b]>2) f = 0;
        if(a == b) f = 0;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    if(!f)
    {
        cout<<"NO"<<endl;
        return;
    }
    ok = 1;
    for(int i = 1; i<=n; i++)
    {
        if(!col[i]) col[i] = 1, dfs(i); //  Dyeing to judge parity 
        if(!ok)
        {
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//    solve();
    int T;
    cin>>T;
    while(T -- )
    {
        solve();
    }
}