题目背景
约翰厌倦了劳作的生活,决定将遗产分给两个儿子,然后云游四方(约翰很疼爱两个儿子,但是偏心大儿子)。
题目描述
约翰是一个农场主,他的农场有 n 块田,编号从 1 到 n,这 n 块田通过 m 条双向道路相连(数据保证这n块田都是联通的),我们假设第 i 块田会产生 2ikg 的收益,现在约翰想把农田的工作全部交给自己的两个孩子,划分方式必须满足以下规则:
- 1.每一块田都需要恰好被分给一个孩子.
- 2.分给两个孩子的农田必须是联通的.就是说对于任意一个孩子在划分给自己的任意一块田,都可以不经过另外一个孩子的田,到达自己的任意一块田.
- 3.划分给两个孩子的收益必须尽可能的相等,如果无法相等,年长的孩子会得到大的那一份.
对于第 ii 块田,如果你要把它分给年长的孩子,请输出A
,否则输出B
.
输入格式
第一行输入两个整数分别代表 n,mn,m
接下来 mm行,每个两个整数u,vu,v,代表这两块农田通过一条双向道路直接相连,数据保证没有自环
输出格式
输出一个长度为 nn 的字符串,代表答案
样例
输入数据 1
3 2
1 3
3 2
Copy
输出数据 1
ABA
Copy
提示
样例解释
我们发现此样例无法使得收益相等,那么于是我们将第 11 和 第 33 块农田分给长子,第 22 块农田分给小儿子,可以使得收益差距最小。
数据范围
2≤n≤3×105,1≤m≤3×1052≤n≤3×105,1≤m≤3×105
可以使用深度优先搜索(DFS)算法对图中的节点进行标记的 C++ 程序。它接受输入的节点数和边数,以及边的信息。然后,它使用DFS算法根据节点的连通性将节点标记为'A'或'B'。
该程序使用一个向量的向量来表示图,使用一个数组 'a' 来存储节点的标记。DFS函数用于根据节点与最后一个节点的连通性来标记节点。
- 程序接受输入的图中节点数和边数。
- 然后,它接受边的输入并相应地填充图。
- 将最后一个节点的标记初始化为 'A',并调用DFS函数来标记其他节点。
- DFS函数根据节点与最后一个节点的连通性来标记节点。
- 最后,程序打印所有节点的标记。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
vector<int>g[N];
int n,m,a[N];
void dfs(int x){
if(a[x]==1){
return;
}
a[x]=2;
for(auto to:g[x]){
if(!a[to]){
dfs(to);
}
}
}
int main() {
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
a[n]=1;
dfs(n-1);
for(int i=1;i<=n;i++){
if(a[i]==2){
cout<<'B';
}else{
cout<<'A';
}
}
return 0;
}