返回信息流我用图的环来做。大神帮看看，哪里错了。
题目：
Problem
You are a teacher at the brand new Little Coders kindergarten. You have N kids in your class, and each one has a different student ID number from 1 through N. Every kid in your class has a single best friend forever (BFF), and you know who that BFF is for each kid. BFFs are not necessarily reciprocal -- that is, B being A's BFF does not imply that A is B's BFF.
Your lesson plan for tomorrow includes an activity in which the participants must sit in a circle. You want to make the activity as successful as possible by building the largest possible circle of kids such that each kid in the circle is sitting directly next to their BFF, either to the left or to the right. Any kids not in the circle will watch the activity without participating.
What is the greatest number of kids that can be in the circle?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of two lines. The first line of a test case contains a single integer N, the total number of kids in the class. The second line of a test case contains N integers F1, F2, ..., FN, where Fi is the student ID number of the BFF of the kid with student ID i.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the maximum number of kids in the group that can be arranged in a circle such that each kid in the circle is sitting next to his or her BFF.
Limits
1 ≤ T ≤ 100.
1 ≤ Fi ≤ N, for all i.
Fi ≠ i, for all i. (No kid is their own BFF.)
Small dataset
3 ≤ N ≤ 10.
Large dataset
3 ≤ N ≤ 1000.
Sample
Input
Output
4
4
2 3 4 1
4
3 3 4 1
4
3 3 4 3
10
7 8 10 10 9 2 9 6 3 3
Case #1: 4
Case #2: 3
Case #3: 3
Case #4: 6
In sample case #4, the largest possible circle seats the following kids in the following order: 7 9 3 10 4 1. (Any reflection or rotation of this circle would also work.) Note that the kid with student ID 1 is next to the kid with student ID 7, as required, because the list represents a circle.
我的代码：
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class DirectedGraphNode {
int label;
ArrayList<DirectedGraphNode> neighbors;
DirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<DirectedGraphNode>();
}
}
public class Main {
public static void main(String[] args) throws FileNotFoundException {
// FileInputStream fis = new FileInputStream("C-small-attempt1 (1).in");
// PrintStream out = new PrintStream(new FileOutputStream("C-small-attempt1 (1).out"));
// System.setIn(fis);
// System.setOut(out);
Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
int t = in.nextInt(); // Scanner has functions to read ints, longs, strings, chars, etc.
for (int i = 1; i <= t; ++i) {
int n = in.nextInt();
ArrayList<DirectedGraphNode> graph = new ArrayList();
for (int k = 1; k <= n; k++) {
DirectedGraphNode node = new DirectedGraphNode(k);
graph.add(node);
}
for (int k = 0; k < n; k++) {
int y = in.nextInt();
graph.get(k).neighbors.add(graph.get(y - 1));
}
ArrayList<DirectedGraphNode> graph2 = new ArrayList(graph);
HashMap<DirectedGraphNode, Integer> map = new HashMap();
//map 用来记录那些成为了别人邻居的点作为多少个邻居，也就是他的入度是多少。
for (DirectedGraphNode g : graph) {
for (DirectedGraphNode nei : g.neighbors) {
if (map.containsKey(nei)) {
map.put(nei, map.get(nei) + 1);
} else {
map.put(nei, 1);
}
}
}
Queue<DirectedGraphNode> queue = new LinkedList();
for (DirectedGraphNode g : graph) {
if (!map.containsKey(g)) {
//不在map里面，说明他的度为0
queue.add(g);
graph2.remove(g);
}
}
int count = queue.size();
// System.out.println(queue.size());
boolean flag = true;
while (!queue.isEmpty() && flag) {
flag = false;
DirectedGraphNode node = queue.poll();
for (DirectedGraphNode node1 : node.neighbors) {
map.put(node1, map.get(node1) - 1);
if (map.get(node1) == 0) {
flag = true;
queue.add(node1);
graph2.remove(node1);
count++;
}
}
}
int add = 0;
if (count == 2) {
for (DirectedGraphNode d : graph2) {
for (DirectedGraphNode g : graph) {
if (!graph2.contains(g) && g.neighbors.contains(d)) {
add++;
break;
}
}
}
}
System.out.println("Case #" + i + ": " + ((n - count) + Math.min(add, 2)));
}
}
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #89656同步于 2016/4/16
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
今天早上Google Code jam 第三题。
YUEYE
2016/4/16镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。