1 问题描述

Description

In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

Input

The first line contains a single integer T, the number of test cases. And followed T cases.

The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.

Output

The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.

Sample Input

13 31 22 33 1

Sample Output

Yes

Source

,zgl & twb

题目链接：

2 解决方案

具体代码如下：

package com.liuzhen.practice;import java.util.ArrayList;import java.util.Scanner;import java.util.Stack;public class Main {    public static int n;  //顶点数    public static int count;    public static int[] DFN;    public static int[] Low;    public static boolean[] inStack;    public static int group;  //强连通分量组    public static int[] belong;    public static Stack
     
       stack;    public static ArrayList
      
       [] map;    public static ArrayList
       
         result = new ArrayList
        
         ();        static class edge {        public int a;        public int b;                public edge(int a, int b) {            this.a = a;            this.b = b;        }    }        @SuppressWarnings("unchecked")    public void init() {        count = 1;        DFN = new int[n + 1];        Low = new int[n + 1];        inStack = new boolean[n + 1];        group = 0;        belong = new int[n + 1];        stack = new Stack
         
          ();        map = new ArrayList[n + 1];        for(int i = 1;i <= n;i++) {            DFN[i] = -1;            Low[i] = -1;            inStack[i] = false;            belong[i] = -1;            map[i] = new ArrayList
          
           (); } } public void TarJan(int start) { DFN[start] = count++; Low[start] = DFN[start]; inStack[start] = true; stack.push(start); int j = start; for(int i = 0;i < map[start].size();i++) { j = map[start].get(i).b; if(DFN[j] == -1) { TarJan(j); Low[start] = Math.min(Low[start], Low[j]); } else if(inStack[j]) { Low[start] = Math.min(Low[start], DFN[j]); } } if(DFN[start] == Low[start]) { group++; do { j = stack.pop(); belong[j] = group; inStack[j] = false; } while(j != start); } } public boolean TopSort(ArrayList
           
            [] lessMap, int[] degree) { int count = 0; Stack
            
              s = new Stack
             
              (); for(int i = 1;i < degree.length;i++) { if(degree[i] == 0) { count++; s.push(i); } } if(count > 1) return false; while(!s.empty()) { int start = s.pop(); count = 0; for(int i = 0;i < lessMap[start].size();i++) { int j = lessMap[start].get(i).b; degree[j]--; if(degree[j] == 0) { count++; s.push(j); } } if(count > 1) return false; } return true; } @SuppressWarnings("unchecked") public void getResult() { for(int i = 1;i <= n;i++) { if(DFN[i] == -1) TarJan(i); } ArrayList
              
               [] lessMap = new ArrayList[group + 1]; int[] degree = new int[group + 1]; for(int i = 1;i <= group;i++) lessMap[i] = new ArrayList
               
                (); for(int i = 1;i < map.length;i++) { for(int j = 0;j < map[i].size();j++) { int a = map[i].get(j).a; int b = map[i].get(j).b; if(belong[a] != belong [b]) { lessMap[belong[a]].add(new edge(belong[a], belong[b])); degree[belong[b]]++; } } } if(TopSort(lessMap, degree)) { result.add("Yes"); } else { result.add("No"); } return; } public static void main(String[] args) { Main test = new Main(); Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t > 0) { t--; n = in.nextInt(); int k = in.nextInt(); test.init(); for(int i = 0;i < k;i++) { int a = in.nextInt(); int b = in.nextInt(); map[a].add(new edge(a, b)); } test.getResult(); } for(int i = 0;i < result.size();i++) System.out.println(result.get(i)); }}

运行结果：

13 31 22 33 1Yes

参考资料：

转载地址：http://rwjmo.baihongyu.com/

你可能感兴趣的文章