c++题目_分财产

题目背景

约翰厌倦了劳作的生活，决定将遗产分给两个儿子，然后云游四方（约翰很疼爱两个儿子，但是偏心大儿子）。

题目描述

约翰是一个农场主，他的农场有 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函数用于根据节点与最后一个节点的连通性来标记节点。

1. 程序接受输入的图中节点数和边数。
2. 然后，它接受边的输入并相应地填充图。
3. 将最后一个节点的标记初始化为 'A'，并调用DFS函数来标记其他节点。
4. DFS函数根据节点与最后一个节点的连通性来标记节点。
5. 最后，程序打印所有节点的标记。

代码：

#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;
}