计蒜客 p 节点 树的遍历

计蒜客 p 节点 树的遍历

​​题目链接​​

思路&题意：

给你n个点，组成一棵树，树必然有n-1边，现在定义p结点，它不小于父亲和儿子的度，求有几个p结点 利用Vector数组建图，注意在java中要对每个元素初始化！！！这里可以单独开一个数组记录父亲，因为是树所以只有一个父亲，也可以直接当初无向图来建。

import java.util.Scanner;import java.util.Vector;public class Main { static long gcd(long a,long b){ return b==0?a:gcd(b,a%b); } public static void main(String[] args) { Scanner cin = new Scanner(System.in); int t = cin.nextInt(); while(t--!=0) { int n = cin.nextInt(); Vector []v = new Vector[1005]; int vis[] = new int[1005]; for(int i = 1;i <= n;i++) { v[i] = new Vector(); } for(int i = 1;i < n;i++) { int x = cin.nextInt(); int y = cin.nextInt(); v[x].add(y); v[y].add(x); vis[x]++; } int flag = 0;int cnt = 0; for(int i = 1;i <= n;i++) { flag = 0; for(int j = 0;j < v[i].size();j++) { int T = v[i].get(j); if(vis[i] < vis[T]) { flag = 1; break; } } if(flag == 0 && v[i].size() != 0) { cnt++; //System.out.println(i); } } System.out.println(cnt); } }} ///// 4 6 60 / 15 4 3 20 // 2 5// 6 8// 6 9// 3 6

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。