#include<iostream> #include<vector> using namespace std; //邻接表建图 static const int N = 100010;
static vector<int>g[N];//本质上是一个二维矩阵 static int n; static int w[N];//记录个数
//第二种dfs方案，建立有向图 int dfs(int u) { // 初始化当前节点的子树节点数目 w[u] = 1; // 遍历所有子节点 for (int v : g[u]) { w[u] += dfs(v); } // 包括当前节点本身 return w[u]; }
//主函数的实现 int main() { cin >> n; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); } //递归遍历 //根节点为1, dfs(1); for (int i = 1; i <= n; i++) { cout << w[i] << ' '; } return 0; }
4 comments
-
zzg_code LV 6 @ 2024-6-24 20:07:35
我知道为什么了，输入里面说的是有a，b之间有一条边，但是没有保证一定是a到b（没有保证a是父节点，b是子节点），有可能是b到a，因此需要添加双向边。
👍 1 -
@ 2024-6-21 22:22:11
试了好多例子，都没问题，不知道哪里出问题了
-
@ 2024-6-21 22:21:42
#include <iostream> #include <vector> #include<algorithm> using namespace std; int fun(vector<vector<int>>& tree,vector<int>& ans,int node) { int temp=1; for(auto &elem:tree[node]) { temp+=fun(tree,ans,elem); } ans[node]=temp; return temp; } int main() { int n; cin>>n; vector<vector<int>> tree(n); vector<int> ans(n); for(int i=0;i<n-1;i++) { int r,l; cin>>r>>l; r--,l--; tree[r].push_back(l); } fun(tree,ans,0); for(auto &elem:ans) { cout<<elem<<" "; } } -
@ 2024-6-21 22:21:36
我也很奇怪，这个题目很简单，就是过不了
- 1
