题目解析
给定每扇门后能通先的门
求出离入口最远的一扇门的距离
解题思路
bfs搜索当前这扇门能到达的门 记录距离
从入口开始去找 最远的一扇门
因为不存在两条路通向同一扇门 所以如果的入点为0
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int N = (int) 1e5, M = N << 1;
static int h[] = new int[N + 10], shu[] = new int[M + 10], ne[] = new int[M + 10], idx;
static int d[] = new int[N + 10];
static boolean user[] = new boolean[N + 10];
static void add(int a, int b)
{
shu[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
static void bfs(int root)
{
LinkedList<Integer> li = new LinkedList<Integer>();
li.add(root);
d[root] = 1;
int max = 0;
int end = 0;
while (li.size() != 0)
{
int u = li.poll();
if (d[u] > max)
{
end = u;
max = d[u];
}
for (int i = h[u]; i != 0; i = ne[i])
{
int j = shu[i];
if (d[j] == 0)
{
d[j] = d[u] + 1;
li.push(j);
}
}
}
out.println(end);
}
public static void main(String[] args) throws IOException
{
int n = ini();
idx = 1;
for (int i = 1; i <= n; i++)
{
int m = ini();
while (m-- > 0)
{
int x = ini();
add(i, x);
user[x] = true;
}
}
int root = 1;
while (user[root])
root++;
bfs(root);
out.flush();
out.close();
}
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(System.out);
static int ini() throws IOException
{
sc.nextToken();
return (int) sc.nval;
}
}