1.

/**
* FWP, Ausgew�hlte Probleme aus dem ACM Programming Contest, WS09 Problem: 615 - Is It A Tree?
* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=556
*
* @author Kratzer Kevin
Dennis Wilfert
* @version 1.0, 12/16/2009
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.140
*/

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;

public class Main {

public static void main(String... args) {
Scanner s = new Scanner(System.in);
ArrayList<int[]> points = new ArrayList<int[]>();
int k = 1;
while (true) {
int start = s.nextInt();
int destination = s.nextInt();
if (start == -1 && destination == -1) {
return;
}
if(start == 0 && destination == 0) {
if(isTree(points) || points.isEmpty()) { // Ist die ArrayList leer muss ... is a tree ausgegeben werden.
System.out.printf("Case %d is a tree.\n",k);
} else {
System.out.printf("Case %d is not a tree.\n",k);
}
points = new ArrayList<int[]>();
k++;
} else {
points.add(new int[] {start,destination});

}

}
}
/*
* There is exactly one node, called the root, to which no directed edges point.
* Every node except the root has exactly one edge pointing to it.
* There is a unique sequence of directed edges from the root to each node.
*/
private static boolean isTree(ArrayList<int[]> points) {
if(points.size() == 0) {
return false;
}
for(int[] destination: points) {
for(int[] point: points) {
if(point != destination)
if(point[0] == destination[0] && point[1] == destination[1]) {
return false;
}
}
}
/*There is exactly one node, called the root, to which no directed edges point.*/
int root = -1;
for(int[] destination: points) {


boolean isRoot = true;
for(int[] point: points) {
if(point != destination) {
if(point[1] == destination[0]) {
isRoot = false;
break;
}
}
}
if(isRoot) {
if(root != -1 && root != destination[0]) {
return false;
}
root = destination[0];
}
}
/*Every node except the root has exactly one edge pointing to it.*/
HashSet<Integer> nodes = new HashSet<Integer>();
for(int[] destination: points) {
if(destination[0] == destination[1]) // Zeigt der Knoten auf sich selbst, ist es kein Baum
return false;
if(destination[1] == root) {
continue;
}
if(nodes.contains(destination[1])) {
return false;
}
nodes.add(destination[1]);
}

/*There is a unique sequence of directed edges from the root to each node.*/
HashSet<int[]> reachablePoints = new HashSet<int[]>();
Stack<int[]> queue = new Stack<int[]>();
for(int[] point: points) {
if(point[0] == root) {
queue.add(point);
}
}

while(queue.size() > 0) {
int[] point = queue.pop();
if(reachablePoints.contains(point)) {
return false;
}
reachablePoints.add(point);
for(int[] newPoint: points) {
if(newPoint != point) {
if(point[1] == newPoint[0]) {
if(queue.contains(newPoint)) {
return false;
}
queue.push(newPoint);
}
}
}
}
return (reachablePoints.size() == points.size());
}


}

2.

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09 Problem: 615 - Is It A Tree?
* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=556
*
* @author Kratzer Kevin
* @version 1.0, 12/23/2009
*
* Method : Ad-Hoc Status : Accepted Runtime: 0.116
*/
public class Main615 {

public static void main(String... args) {
Scanner s = new Scanner(System.in);
ArrayList<int[]> points = new ArrayList<int[]>();
int k = 1;
while (true) {
int start = s.nextInt();
int destination = s.nextInt();
if (start == -1 && destination == -1) {
return;
}
if(start == 0 && destination == 0) {
if(isTree(points)) {
System.out.printf("Case %d is a tree.\n",k);
} else {
System.out.printf("Case %d is not a tree.\n",k);
}
points = new ArrayList<int[]>();
k++;
} else {
points.add(new int[] {start,destination});
}

}
}
/*
* There is exactly one node, called the root, to which no directed edges point.
* Every node except the root has exactly one edge pointing to it.
* There is a unique sequence of directed edges from the root to each node.
*/
private static boolean isTree(ArrayList<int[]> points) {
if(points.size() == 0) {
return true;
}
for(int[] point: points) {
if(point[0] == point[1]) {
return false;
}
}
for(int[] destination: points) {
for(int[] point: points) {
if(point != destination)
if(point[0] == destination[0] && point[1] == destination[1]) {
return false;
}
}
}
/*There is exactly one node, called the root, to which no directed edges point.*/
int root = -1;
for(int[] destination: points) {
boolean isRoot = true;
for(int[] point: points) {
if(point != destination) {
if(point[1] == destination[0]) {
isRoot = false;
break;
}
}
}
if(isRoot) {
if(root != -1 && root != destination[0]) {
return false;
}
root = destination[0];
}
}
/*Every node except the root has exactly one edge pointing to it.*/
HashSet<Integer> nodes = new HashSet<Integer>();
for(int[] destination: points) {
if(destination[1] == root) {
continue;
}
if(nodes.contains(destination[1])) {
return false;
}
nodes.add(destination[1]);
}

/*There is a unique sequence of directed edges from the root to each node.*/
HashSet<int[]> reachablePoints = new HashSet<int[]>();
Stack<int[]> queue = new Stack<int[]>();
for(int[] point: points) {
if(point[0] == root) {
queue.add(point);
}
}

while(queue.size() > 0) {
int[] point = queue.pop();
if(reachablePoints.contains(point)) {
return false;
}
reachablePoints.add(point);
for(int[] newPoint: points) {
if(newPoint != point) {
if(point[1] == newPoint[0]) {
if(queue.contains(newPoint)) {
return false;
}
queue.push(newPoint);
}
}
}
}
return (reachablePoints.size() == points.size());
}


}