[code source] daily question farmland Division

2022.05.12

Topic link ： Farmland division - subject - Daimayuan Online Judge 

Title Description

John is a farmer , His farm has n Block field , Number from  1 To  n, this  n Block field pass  m A two-way road connects ( The data guarantees that n All fields are connected ), Let's assume that No i A field will produce  2^i kg Revenue , Now John wants to leave all the farm work to his two children , The division method must meet the following rules :

1. Every field needs to be given to just one child .

2. The farmland allocated to the two children must be connected . That is to say, for any child in any field allocated to him , Can not pass through another child's field , Reach any of your fields .

3. The benefits divided between the two children must be as equal as possible , If it cannot be equal , Older children get the bigger share .

For the first  i Block field , If you're going to give it to older children , Please export A, Otherwise output B.

Topic input

On the first line, enter two integers representing  n,m  Next  m That's ok , Every two integers u,v, It means that the two farmland are directly connected by a two-way road , Data guarantees that there are no double edges and self rings

Topic output

Output a string , For the answer

The sample input 1

3 2
1 3
3 2

Sample output 1

ABA

The sample input 2

6 6
3 5
2 6
1 3
3 6
5 1
4 6

Sample output 2

BABABA

Data range

2≤n≤3e5,1≤m≤3e5

analysis ：

The title requires that n Each field is divided into two parts , And each part needs to be connected .

Analyze the income of each field , Right. i  The income of this field is 2^i, front （1~i-1) The sum of blocks is at most 2^i-1, That is to say, even if you take 1~i-1 I didn't get a piece i The benefits of each piece are great , That is, the larger the number , The bigger the proceeds. . So for n Block plot , To divide evenly , The first n The piece must be for A Of , In the case that Unicom is satisfied, it will be distributed to B The more, the better , And the larger the number, the better , therefore n-1 Must be assigned to A.

therefore , Just connect with n-1 The connected fields are allocated to B Give the rest to A（ Union checking set ）. 

See the code for details. ：

#include <bits/stdc++.h>
using namespace std;
int n, m;
int far[300009];
inline int find(int x) // lookup 
{
    return (far[x] == x) ? x : far[x] = find(far[x]);
}
inline void unionn(int x, int y) // Merge 
{
    x = find(x);
    y = find(y);
    if (x != y)
    {
        if (x < y) // In order to make n-1 The father of Unicom's number is n-1, So merge the smaller ones into the larger ones 
            swap(x, y);
        far[y] = far[x]; // take y My father became x Father 
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        far[i] = i; // And search set initialization 
    while (m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x == n || y == n) // B Our fields cannot pass A In the field to reach Unicom 
                              //  Topics ensure connectivity , Not with B Unicom will definitely work with A Unicom 
            continue;
        else
            unionn(x, y); // Merge 
    }
    for (int i = 1; i <= n; i++)
        if (find(i) == n - 1) // And B Unicom is assigned to B
            cout << "B";
        else
            cout << "A";
}