
#include <bits/stdc++.h>
using
namespace
std;
void
add_edge(vector<
int
> adj[],
int
u,
int
v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void
dfs(vector<
int
>& parent,
vector<
int
> adj[],
int
u,
int
par = -1)
{
parent[u] = par;
for
(
auto
child : adj[u]) {
if
(child != par)
dfs(parent, adj, child, u);
}
}
void
countSmallerAncestors(
vector<
int
> adj[],
int
n)
{
vector<
int
> parent(
int
(1e5), 0);
dfs(parent, adj, 1);
for
(
int
i = 1; i <= n; i++) {
int
node = i;
int
cnt = 0;
while
(parent[node] != -1) {
if
(parent[node] < i)
cnt += 1;
node = parent[node];
}
cout << cnt <<
" "
;
}
}
int
main()
{
int
N = 6;
vector<
int
> adj[
int
(1e5)];
add_edge(adj, 1, 5);
add_edge(adj, 1, 4);
add_edge(adj, 4, 6);
add_edge(adj, 5, 3);
add_edge(adj, 5, 2);
countSmallerAncestors(adj, N);
return
0;
}
0 comments:
Post a Comment