试题 历届试题 发现环

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。

不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。

为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？
输入格式
　　第一行包含一个整数N。
　　以下N行每行两个整数a和b，表示a和b之间有一条数据链接相连。

对于30%的数据，1 <= N <= 1000
　　对于100%的数据, 1 <= N <= 100000， 1 <= a, b <= N

输入保证合法。
输出格式
　　按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。
样例输入
5
1 2
3 1
2 4
2 5
5 3
样例输出
1 2 3 5

分析：
大方向分为两步，
第一步，使用并查集将所有的节点进行归类分组，找到每一个节点的父节点。将原本就已经是同一个父节点的两个节点保存起来，

这样讲解：首先1和2进行连接了，把2的父节点设置成1，下一条记录大仙1和3是相连的，这时候将3的节点设置成为1，下一条记录，发现2的父节点是1，3的父节点也是1，这时候我们就知道中间一定形成了环，但是我们这时候不知道这个环中间有哪些节点，我们只知道这个环中肯定是包括2和3。每一次将这些具有相同父节点的记录给存储下来，这里我使用了hashset。

第二步，在上一步中间我们将所有的记录都保存下来了，我们这样想，以1位起点，3为终点，使用dfs从1开始找到终点是3的路径。

如果仅仅是普通的dfs的话，仅仅只能找到一条路径。比如上面这个图，我们需要找到从5开始到3的路径，这时候我们发现只能找到一条路径。因为访问过3这个顶点之后，3就会被设置成为已经访问，之后再去找的时候就卡死了。
这里我使用可一个hashset将路径记录下拉，如果当前的路径之前并没有走过就继续（这里自己打一下代码会深刻很多）
将所有的路径记录下来之后再把么一个节点记录下来，题目要求的是需要排序并且要去重，最好的就是使用TreeSet。

丢上垃圾的30分代码，（剩下的都已经超过内存了，哎）
供入门新手看看。

package 第八届C语言A组;

import java.util.HashSet;
import java.util.Scanner;
import java.util.TreeSet;

public class 发现环 {
	public static int a;
	public static int shu[];
	public static int graph[][];
	public static HashSet<Ring> hashSet = new HashSet<>();
	public static HashSet<String> traceHashSet = new HashSet<>();
	public static TreeSet<Integer> resSet = new TreeSet<>();
	public static void main(String[] args) {
		Scanner input =new Scanner(System.in);
		a =input.nextInt();
		graph = new int[a+1][a+1];
		shu = new int [a+1];
		//初始化
		for (int i = 1; i < shu.length; i++) {
			shu[i] = i;
		}
		for (int i = 0; i < a; i++) {
			int x = input.nextInt();
			int y = input.nextInt();
			graph[x][y] = 1;
			graph[y][x] = 1;
			merge(x, y);
		}
		for(Ring key :hashSet) {
			int x = key.px;
			int y = key.py;
			boolean tflag [] = new boolean[a+1];
			dfs(x, y, x+"", tflag);
		}
		for(int key : resSet) {
			System.out.print(key+" ");
		}
	}
	//起点是x,终点是y，找到从x到y的路径ArrayList<Integer> list
	public static void dfs(int x,int y,String string,boolean flag[]) {
		if (x == y) {
			traceHashSet.add(string);
			String name[] = string.split("-");
			for (int i = 0; i < name.length; i++) {
				resSet.add(Integer.parseInt(name[i]));
			}
			return;
		}
		flag[x] = true;
		int w = getFirst(x);
		while (w != -1) {
			if (flag[w] == false || (w == y && traceHashSet.contains(string+"-"+y) == false)) {
				flag[w] = true;
				dfs(w, y, string+"-"+w, flag);
			}else {
				w = getNext(x, w);
			}
		}
	}
	public static int getFirst(int index) {
		for (int i = 0; i < graph.length; i++) {
			if (graph[index][i] == 1) {
				return i;
			}
		}
		return -1;
	}
	public static int getNext(int index,int p) {
		for (int i = p+1; i < graph.length; i++) {
			if (graph[index][i] == 1) {
				return i;
			}
		}
		return -1;
	}
	public static  int getF(int v) {
		if (shu[v] == v) {
			return v;
		}else {
			shu[v] = getF(shu[v]);
			return shu[v];
		}
	}
	public static void merge(int a,int b) {
		int t1 = getF(a);
		int t2 = getF(b);
		if (t1 != t2) {
			shu[t2] = t1;
		}else {
			hashSet.add(new Ring(a, b));
		}
	}
}
class Ring{
	int px;
	int py;
	public Ring(int px,int py) {
		super();
		this.px = px;
		this.py = py;
	}
}