疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Java实例拓扑排序


 

   有一群人,打乒乓球比赛,两两捉对撕杀,每两个人之间最多打一场比赛。

  球赛的规则如下:

  如果A打败了B,B又打败了C,而A与C之间没有进行过比赛,那么就认定,A一定能打败C。

  如果A打败了B,B又打败了C,而且,C又打败了A,那么A、B、C三者都不可能成为冠军。

  根据这个规则,无需循环较量,或许就能确定冠军。你的任务就是面对一群比赛选手,在经过了若干场撕杀之后,确定是否已经实际上产生了冠军。

  Input

  输入含有一些选手群,每群选手都以一个整数n(n<1000)开头,后跟n对选手的比赛结果,比赛结果以一对选手名字(中间隔一空格)表示,前者战胜后者。如果n为0,则表示输入结束。

  Output

  对于每个选手群,若你判断出产生了冠军,则在一行中输出“Yes”,否则在一行中输出“No”。

  Sample Input

  3

  Alice Bob

  Smith John

  Alice Smith

  5

  a c

  c d

  d e

  b e

  a d

  0

  Sample Output

  Yes

  No

  Author

  qianneng

  Source

  迎接新学期——超级Easy版热身赛

  说是拓扑排序还不如说是一个简单的STL。

  题目主要需要解决的是:判断是否只有一个人未被打败,而最简单的方法莫过于STL里的Set容器。

  一个用来存放所有的比赛人员,另一个则是存放那些被打败的人。

  如果打败的人数 = 总人数 -- 1 ,那么就存在一个冠军!

  import java.util.HashSet;

  import java.util.Scanner;

  import java.util.Set;

  public class hdu2094产生冠军_拓扑排序 {

  public static void main(String[] args) {

  // TODO Auto-generated method stub

  Scanner sc = new Scanner(System.in);

  while(true){

  int N=sc.nextInt();

  if(N==0)break;

  Set set = new HashSet();

  Set key = new HashSet();

  set.clear();key.clear();

  String s;

  for(int i=0;i

  set.add(sc.next());

  set.add(s=sc.next());//统计所有的不同结点

  key.add(s);//被打败的结点

  }

  if(set.size()-key.size()==1)//还剩下一个未被打败

  System.out.println("Yes");

  else

  System.out.println("No");

  }

  }

  }

  import java.util.HashSet;

  import java.util.Scanner;

  import java.util.Set;

  public class hdu2094产生冠军_拓扑排序 {

  public static void main(String[] args) {

  // TODO Auto-generated method stub

  Scanner sc = new Scanner(System.in);

  while(true){

  int N=sc.nextInt();

  if(N==0)break;

  Set set = new HashSet();

  Set key = new HashSet();

  set.clear();key.clear();

  String s;

  for(int i=0;i

  set.add(sc.next());

  set.add(s=sc.next());//统计所有的不同结点

  key.add(s);//被打败的结点

  }

  if(set.size()-key.size()==1)//还剩下一个未被打败

  System.out.println("Yes");

  else

  System.out.println("No");

  }

  }

  }