题目描述
思路–多叉树(图)的遍历
链式前向星,st[j]
目的是让每个节点只遍历一遍
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = N *2;
int n,m;
int h[N],e[M],ne[M],idx;
bool st[N];//一般的题目每个点只需要遍历一次,所以开一个bool数组
void add(int a, int b)//头插法插入链表
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;//非常重要的一句话!※相当于:idx就是每个节点独一无二的“身份证”,h[]始终储存的是头节点的身份证。
}
void dfs(int u)
{
st[u] = true;
for (int i = h[u]; i != -1; i = ne[i])//单链表遍历
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
int main()
{
memset(h, -1, sizeof h);//头节点初始化:所有h都指向-1(注意:h存储的是指向头节点的指针!important)
dfs(1);
}
本题解法
核心: 就是把一个普通的白板树(w[j]=1
)变成一颗满树(w[j]=j
)
问题: 每次操作一棵子树所有节点w[j]=w[j]+1
,一共需要多少次操作?
看注释吧,写不动了,想了一中午......
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n, cnt, tmp;
int e[N], w[N], ne[2 * N], h[2 * N], idx;
bool st[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u, int tmp) {
// 记录父节点的tmp差值, 本层单链表的遍历父节点差值father不变
int father = tmp;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i]; // 该节点
int k = e[ne[i]]; // 下一个节点
// 该节点的操作次数,使得该节点w[j]=j
// 因为父节点的操作会影响到子节点,所以父节点的tmp需要累加下来
tmp = j - (w[j] + father);
w[j] += tmp + father;
// cout << j << ' ' << tmp << ' ' << w[j] << endl; // 打表看一下
// 如果j > k,说明有子树,递归查询子树
if (j > k)
dfs(j, tmp);
cnt += tmp; // 记录操作次数
}
}
int main() {
cin >> n;
// 初始化白板w[j]=1的树
memset(h, -1, sizeof h);
for (int i = 1; i < n; i ++ ) {
int a, b;
cin >> a >> b;
add(a, b);
w[i] = 1;
}
w[n] = 1;
dfs(1, 0); // 从根节点1, tmp=0开始dfs
// for (int i = 1; i <= n; i ++ ) cout << w[i] << ' ';
// cout << endl;
cout << cnt << endl;
return 0;
}
ACM大佬解法—有点问题
二维map有点吊