首页 > 试题广场 >

叶子删除计划

[编程题]叶子删除计划

热度指数：466 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小度给定你一棵拥有n个点的树，每次删去当前所有的叶子节点（即度数小于等于1的节点）和叶子节点所连接的边，直到所有的点都被删除了为止。

你需要对于每个点，求出它是第几次操作中被删除的。

输入描述:

第一行一个数字，表示树上节点个数 
接下来n - 1行，每行两个数字，表示树上的一条边。

输出描述:

一行n个数字，第i个数字表示节点i在第几次操作中被删除。

示例1

输入

输出

2 2 1 1 1

示例2

输入

输出

2 1 1 1

算法知识视频讲解

难受啊兄弟

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


class Node {
    int num;
    List<Node> friend;
    Boolean deleted = false;

    public Node() {
        this.friend = new ArrayList<>();
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node();
        }
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            nodes[a].friend.add(nodes[b]);
            nodes[b].friend.add(nodes[a]);
            nodes[a].num++;
            nodes[b].num++;
        }

        int count = 1;
        int[] res = new int[n];
        int flag = 0;
        while (flag < n) {
            List<Node> list = new ArrayList<>();
            for (int i = 0; i < nodes.length; i++) {
                if (nodes[i].deleted) continue;
                if (nodes[i].num <= 1) {
                    nodes[i].num -= 1;
                    res[i] = count;
                    list.add(nodes[i]);//在一轮遍历后，统一处理被删除节点地friend的num值。如果在这里直接处理，会屏蔽掉后面
                    flag++;
                    nodes[i].deleted = true;
                }
            }
            for (Node node : list) {
                for (Node aFriend : node.friend) {
                    aFriend.num--;
                }
            }
            count++;
        }
        for (int re : res) {
            System.out.print(re + " ");
        }
    }
}

发表于 2022-09-13 01:08:18 回复(0)

C/C++

zhangbw_

C++ 模拟

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
vector<int> g[maxn];
int ans[maxn], deg[maxn], vis[maxn];

int main() {
    int n, u, v; cin >> n;
    for (int i = 1; i <= n - 1; ++i) {  // 建立邻接表，统计节点度数
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++, deg[v]++;
    }
    vector<int> q;  // 保存的是节点度数小于等于1的节点
    for (int i = 1; i <= n; ++i) if (deg[i] <= 1) q.push_back(i), vis[i] = true;
    int count = 0;
    while (!q.empty()) {
        count++;
        vector<int> tmp;    // 保存新产生的度数小于等于1的节点
        for (auto u : q) {
            ans[u] = count;
            for (int v : g[u]) {    // 删除节点及对应的边
                if (!vis[v] && --deg[v] <= 1) tmp.push_back(v), vis[v] = true; 
            }
        }
        q = tmp;
    }
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);

    return 0;
}

编辑于 2023-03-25 08:53:38 回复(0)

Java

半醉77

import java.util.*;
public class Main{
public static class Node{   //静态内部类
        public List<Node> list= new ArrayList<>(); //树除根节点就一个父啊，是图的话就可以多个，用Node类型的list存  
        public int num = 0;                              //存节点的度，用List.size()方法更新很麻烦,remove后size和索引也变了
        boolean flag = false;                                //节点是否删除
    }
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = n;
        int time = 1;
        int[] res = new int[n+1];
        Node[] nodes = new Node[n+1];
        for(int i = 0; i < n+1; ++i){   //Node[]初始化必要
            Node node = new Node();
            nodes[i] = node;
        }
        while(sc.hasNext()){   //相当于 for(int i = 0; i < n-1; i++) 
            int a = sc.nextInt();
            int b = sc.nextInt();
            nodes[a].list.add(nodes[b]); 
            nodes[b].list.add(nodes[a]);  //数组下标即是节点号，不用属性value了
            nodes[a].num++;
            nodes[b].num++;
        }
        while(count > 0){
            List<Node> levelNode = new ArrayList<>();       //存这次删除的节点
            for( int i = 1; i < n+1; ++i){   //不能从0开始
  			 //定义：树入度<=1(根节点是0，其他都是1),叶子节点出度=0。故叶子节点的度<=1且没有删除就该删除
                if(nodes[i].num <= 1 && !nodes[i].flag){
                    res[i] = time;
                    nodes[i].flag = true;
                    levelNode.add(nodes[i]);        //将被删除的节点加入链表，在后面的遍历里更新
                    count--;                       
                }
            }
            //将这次删除的节点的关联节点的数据更新
            for(Node node : levelNode){
                for(Node i : node.list)
                    i.num--;       
            }
            time++;       
        }
        for( int i = 1; i < n; ++i){
            System.out.print(res[i]+" ");   //输出示例有空格要求
        }
        System.out.print(res[n]);
    }
}

发表于 2021-09-25 15:21:55 回复(0)

quincy_sky

import java.util.*;
import java.util.Scanner;
import java.lang.Math;
import java.util.ArrayList;

public class Main{
    static int N = 200010;
    static int[] e, ne, h;
    static int[] d;
    static int index;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        e = new int[N];
        ne = new int[N * 2];
        h = new int[N];
        d = new int[n + 1];
        Arrays.fill(ne, -1);
        Arrays.fill(h, -1);
        int m = n  - 1;
        while ((m--) > 0) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            add(a, b);
            add(b, a);
            d[a]++;
            d[b]++;
        }
        boolean[] st = new boolean[n + 1];
        int[] res = new int[n];
        int[] que = new int[N];
        int tail = -1;
        int head = 0;
        for (int i = 1; i <= n; i++) {
            if (d[i] == 1) {
                que[++tail] = i;
                st[i] = true;
            }
        }
        int step = 1;
        while (tail >= head) {
            int size = tail - head + 1;
            for (int i = 0; i < size; i++) {
                int cur = que[head++];
                res[cur - 1] = step;
                for (int j = h[cur]; j != -1; j = ne[j]) {
                    int val = e[j];
                    if (!st[val]) {
                        d[val]--;
                        if (d[val] == 1 || d[val] == 0) {
                            que[++tail] = val;
                            st[val] = true;
                        }
                    }
                }
            }
            ++step;
        }

        for (int i = 0; i < n; i++) {
            System.out.print(res[i]);
            if (i != n -1) System.out.print(" ");
        }



    }
    public static void add(int a, int b) {
        e[index] = b;
        ne[index] = h[a];
        h[a] = index++; 
    }
    
}

发表于 2023-03-16 16:47:02 回复(0)

细致的烤冷面在刷题

import java.util.Scanner;
import java.util.Queue;
import java.util.ArrayList;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int[] degree=new int[n];
int[] res=new int[n];
boolean[] deleted=new boolean[n];
ArrayList<ArrayList<Integer>> array=new ArrayList<>();
for(int i=0;i<n;++i){
array.add(new ArrayList<Integer>());
}
while(scanner.hasNext()){
int a=scanner.nextInt();
int b=scanner.nextInt();
array.get(a-1).add(b-1);
array.get(b-1).add(a-1);
degree[a-1]++;
degree[b-1]++;
}
int count=0;
int num=n;
while(num>0){
count++;
ArrayList<Integer> list=new ArrayList<>();
for(int i=0;i<n;++i){
if(degree[i]<=1&&!deleted[i]){
degree[i]--;
res[i]=count;
deleted[i]=true;
list.add(i);
num--;
}
}
for(int i:list){
for(int e:array.get(i)){
degree[e]--;
}
}
}
scanner.close();
for(int e:res){
System.out.print(e+" ");
}
}
}

发表于 2023-03-11 15:20:52 回复(0)

C/C++

aidehuaerzi

#include <bits/stdc++.h>

using namespace std;

queue<pair<int,int>>q;
vector<int>edge[100005];
int d[100005] = {0},ans[100005];
int main()
{
    int n,u,v;
    cin >> n;
    for(int i = 1; i < n; i++) {
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) {
        d[i] = edge[i].size(); 
        if(d[i] <= 1) {
            q.push({i,1});
        }
    }
    while(!q.empty()) {
        auto it = q.front();
        q.pop();
        ans[it.first] = it.second;
        for(int i = 0; i < edge[it.first].size(); i++) {
            d[edge[it.first][i]]--;
            if(d[edge[it.first][i]] == 1)  {
                q.push({edge[it.first][i],it.second+1});
                ans[edge[it.first][i]] = it.second + 1;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

发表于 2023-02-20 11:45:28 回复(0)

等oc的小松鼠很矫健

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] du = new int[n + 1];
        int[] visited = new int[n + 1];

        LinkedList<Integer>[] edges = new LinkedList[n + 1];
        for (int i = 0; i <= n; i++) {
            edges[i] = new LinkedList<>();
        }
        for (int i = 1; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            edges[a].add(b);
            edges[b].add(a);
            du[a] ++;
            du[b] ++;
        }
        int del = 0;
        int time = 1;
        int[] ans = new int[n + 1];
        while (del < n) {
            List<Integer> arr = new ArrayList<>();
            for (int i = 1; i <= n; i++) {
                if (du[i] == 1 && visited[i] == 0) {
                    arr.add(i);
                    visited[i] = 1;
                    del++;
                    ans[i] = time;
                }
            }

            for (int i : arr) {
                for (int neighbor : edges[i]) {
                    du[neighbor]--;
                }
            }
            time++;
        }
        for (int i = 1; i <= n; i++) {
            System.out.print(ans[i]);
            System.out.print(" ");
        }
    }
}

只能通过60%

发表于 2022-04-10 15:13:41 回复(0)

Lason0104

import java.util.*;

/**
 * @author hit-eason
 * @version 1.0
 * @date 2021/9/6 21:39
 */
public class Main{
    public static class Node{
        public List<Node> parents = new ArrayList<>();      //未通过的测试用例发现一个节点可以有多个父亲，故用链表存节点的父亲
        public List<Node> kids = new ArrayList<>();         //尽管按照测试用例貌似一个节点只有一个儿子，但是用链表存不会错
        public int outNum = 0;                              //另开个整型存节点出度，如果用List.size()之类方法更新很麻烦
        public int inNum = 0;                               //节点入度
        boolean flag = true;                                //节点是否已被删除
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = n;
        int storey = 1;
        int[] res = new int[n];
        Node[] nodes = new Node[n];
        //开数组存n个节点
        for(int i = 0; i < n; ++i){
            Node node = new Node();
            nodes[i] = node;
        }
        //根据后续读入行更新节点入度出度、父节点子节点
        while(sc.hasNext()){
            int from = sc.nextInt();
            int to = sc.nextInt();
            nodes[from-1].outNum++;
            nodes[to-1].inNum++;
            nodes[from-1].kids.add(nodes[to-1]);
            nodes[to-1].parents.add(nodes[from-1]);
        }
        //count控制是否已删除所有节点
        while(count > 0){
            List<Node> levelNode = new ArrayList<>();       //存这层删除的节点，必须在for循环遍历后再去50行的levelNode遍历里更新，否则一边删一边更新会删除后面层的节点
            for( int i = 0; i < n; ++i){
                //入度+出度不大于1就该删除，并且用flag判断是否已删除过，防止重复给结果赋值
                if((nodes[i].outNum + nodes[i].inNum) <= 1 && nodes[i].flag){
                    res[i] = storey;
                    nodes[i].flag = false;
                    levelNode.add(nodes[i]);        //将被删除的节点加入链表，在后面的遍历里更新
                    count--;                        //循环结束条件更新，即剩余未删除的节点数
                }
            }
            //将这层删除的节点的关联节点的数据更新
            for(Node node : levelNode){
                for(Node parent : node.parents)
                    parent.outNum--;
                for(Node kid : node.kids)
                    kid.inNum--;
            }
            storey++;       //层数加一
        }
        for( int i = 0; i < n-1; ++i){
            System.out.print(res[i]+" ");
        }
        System.out.print(res[n-1]);
    }
}

发表于 2021-09-07 09:04:58 回复(0)

牛客468857724号

n = int(input())

# 初始化邻接表
edge_table = dict()
for k in range(n):
    edge_table[k] = set()

# 输入边的信息
for _ in range(n-1):
    u, v = [int(i)-1 for i in input().split()]
    edge_table[u].add(v)
    edge_table[v].add(u)

# 找到可删除的节点
rmv_lst = set()
for i, elm in edge_table.items():
    if len(elm) < 2:
        rmv_lst.add(i)

res = [0]*n
next_candidate = set()
for cnt in range(1, 100000):                                    # 使用cnt记录这是第几次迭代
    if len(rmv_lst) == 0:                                    # 如果没有可删除节点，就结束循环
        break

    next_candidate.clear()                   # 清空下一次可删除的节点的候选列表
    for rmv in rmv_lst:
        for other in edge_table[rmv]:
            edge_table[other].remove(rmv)                # 移除与被删除节点相连的边
            next_candidate.add(other)                    # 将候选节点加入到候选列表中
        res[rmv] = cnt                                     # 记录此节点是第几次删除的

    # 清空可删除节点列表，找出候选列表中可删除的节点放入可删除节点列表中
    rmv_lst.clear()
    for cddt in next_candidate:
        # 还没有被删除，且边的个数小于2的节点为可删除节点
        if res[cddt] == 0 and len(edge_table[cddt]) < 2:
            rmv_lst.add(cddt)

print(" ".join(map(str, res)))

发表于 2021-09-06 23:47:05 回复(0)