/*
??Author:lxrmido
??Website:buzhuanggeek.com
??Edit:GVIM_073
??Date:2011/09/11
*/
import?javax.swing.*;
import?java.util.regex.Pattern;
class?hw_14_2{
	private?static?boolean?points[][];
	private?static?int?nop;
	private?static?int?stack[];
	private?static?int?cur_sp?=?0;
	private?static?StringBuilder?route?=?new?StringBuilder（）;
	private?static?StringBuilder?routem?=?new?StringBuilder（）;
	private?static?void?push（int?elem）{
		stack[cur_sp++]?=?elem;
	}
	private?static?int?pop（）{
		return?stack[--cur_sp];
	}
	private?static?boolean?exist（int?elem）{
		for（int?i?=?0;?i?			if（stack[i]?==?elem）
				return?true;
		}
		return?false;
	}
	private?static?void?trace（int?cp）{
		push（cp）;
		boolean?zombie?=?true;
		boolean?mesh?=?false;
		for（int?i?=?0;?i?			if（points[cp][i]?==?true）{
				if（!exist（i））{
					zombie?=?false;
					trace（i）;
				}else?if（i?==?stack[0]）{
					mesh?=?true;
				}
			}
		}
		if（zombie?&&?cur_sp?==?nop）{
			if（mesh）{
				push（stack[0]）;
				addRoute（routem）;
				pop（）;
			}else{
				addRoute（route）;
			}
		}
		pop（）;
	}
	private?static?void?addRoute（StringBuilder?Route）{
		StringBuilder?tmprt?=?new?StringBuilder（）;
		for（int?i?=?cur_sp-1;?i?>=?0;?i--）{
			tmprt.append（stack[i]）;
			if（i?!=?0）
				tmprt.append（“-“）;			
		}
		tmprt.append（“\n“）;
		if（Route.indexOf（tmprt.toString（））?			for（int?i?=?0;?i?				Route.append（stack[i]）;
				if（i?!=?cur_sp-1）
					Route.append（“-“）;
			}
			Route.append（“\n“）;
		}
	}
	public?static?void?main（String[]?args）{
		String?tmp?=?JOptionPane.showInputDialog（null?“請(qǐng)輸入無(wú)向圖的結(jié)點(diǎn)數(shù)：“）;
		while（!（tmp.matches（“\\d+“）））{
			tmp?=?JOptionPane.showInputDialog（null?“輸入有誤，請(qǐng)重新輸入有向圖的結(jié)點(diǎn)數(shù)：“）;
		}
		nop?=?Integer.parseInt（tmp）;
		if（nop?==?1）{
			JOptionPane.showMessageDialog（null?“結(jié)點(diǎn)數(shù)為1，故此圖為歐拉圖，歐拉通路、回路均為?0?。“）;
			System.exit（0）;
		}
		points?=?new?boolean[nop][nop];
		stack?=?new?int[nop*2];
		String?tmpary[];
		while（（tmp?=?JOptionPane.showInputDialog（null?“請(qǐng)輸入無(wú)向路徑，結(jié)點(diǎn)以數(shù)字表示以任意符號(hào)或空格分隔（如?0-1-2-3不再輸入點(diǎn)取消：“））?!=?null）{
			boolean?eftv?=?true;
			if（!（tmp.matches（“\\d.*“）））{
				JOptionPane.showMessageDialog（null?“含有不存在的結(jié)點(diǎn)，本路徑無(wú)效！“）;
				continue;	
			}
			Pattern?p?=?Pattern.compile（“\\D+“）;
			tmpary?=?p.split（tmp）;
			for（int?i?=?0;?i?				if（Integer.parseInt（tmpary[i]）?>=?nop）{
					JOptionPane.showMessageDialog（null?“含有不存在的結(jié)點(diǎn)，本路徑無(wú)效！“）;
					eftv?=?false;
					break;
				}
			}
			if（!eftv）{
				eftv?=?true;
				continue;
			}
			for（int?i?=?0;?i?				points[Integer.parseInt（tmpary[i]）][Integer.parseInt（tmpary[i+1]）]?=?true;
			}
		}
		stack=?new?int[nop*2];
		for（int?i?=?0;?i?			push（i）;
			for（int?j?=?0;?j?				if（points[i][j]?==?true）{
					trace（j）;
				}
			}
			pop（）;
		}
		if（route.length（）?>?1）{
			JOptionPane.showMessageDialog（null?“所有歐拉通路（不含回路）為：\n“+route）;
			if

?屬性????????????大小?????日期????時(shí)間???名稱(chēng)
-----------?---------??----------?-----??----

?????文件???????3403??2011-09-23?22:31??2\hw_14_2.class

?????文件???????3418??2011-09-11?18:39??2\hw_14_2.java

?????目錄??????????0??2011-09-23?22:30??2

-----------?---------??----------?-----??----

?????????????????6821????????????????????3