思想
利用dfs()计算手下的时候要记得加1(当前搜索到的手下)。
代码
import java.io.*;
import java.util.Arrays;
public class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = 100010, idx= 0;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] cnt = new int[N]; //i号的手下个数
static boolean[] has_f = new boolean[N];//是否有父节点
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
public static void add(int a, int b){
e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
//搜索u号的手下个数
public static int dfs(int u){
int res = 0; //手下数量
for(int i=h[u]; i!=-1; i=ne[i]){
int j = e[i];
res += dfs(j)+1; //j本身算一个手下
}
return cnt[u] = res;
}
public static void main(String[] args)throws IOException{
int n = nextInt(), m = nextInt()-1; //编号从0开始,方便排序
Arrays.fill(h, -1);
Integer[] id = new Integer[n]; //id[i]存储排名第i的人是几号
for(int i=0; i<n; i++) id[i] = i; //初始化
for(int i=1; i<n; i++){
int a = nextInt()-1, b = nextInt()-1;
has_f[a] = true;
add(b, a);
}
int root = 0;
while(has_f[root]) root++;
dfs(root);
Arrays.sort(id, (o1, o2)->cnt[o1]==cnt[o2]?o1-o2:cnt[o2]-cnt[o1]);
for(int i=0; i<n; i++){
if(id[i]==m){
out.println(i+1);
break;
}
}
out.flush();
out.close();
}
}