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
1
3 3
1 2
2 3
3 1
Sample Output
Yes
中文说明
为了让他们的儿子勇敢，嘉嘉和风把他们带到一个大山洞。这个洞穴有N个房间，还有连接一些房间的单向走廊。每次，风都会选择两个房间x和y，并要求他们的一个小儿子从一个房间到另一个房间。儿子可以从X到Y，也可以从Y到X。Wind承诺她的任务都是可能的，但实际上她不知道如何决定任务是否可能。为了让她的生活更轻松，贾佳决定选择一个洞穴，在那里每对房间都是一个可能的任务。给定一个山洞，你能告诉佳佳风是否可以随意选择两个房间而不必担心什么吗？
输入
第一行包含一个整数t，即测试用例的数量。并跟踪T案。
每种情况的第一行包含两个整数n，m（0<n<1001，m<6000），洞穴中房间和走廊的数量。下一条M线分别包含两个整数u和v，表示有一条走廊直接连接u和v房间。
输出
输出应包含T行。如果洞穴具有上述财产，则写“是”，否则写“否”。
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<Integer> stack;
public static ArrayList<edge>[] map;
public static ArrayList<String> result = new ArrayList<String>();
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<Integer>();
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<edge>();
}
}
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<edge>[] lessMap, int[] degree) {
int count = 0;
Stack<Integer> s = new Stack<Integer>();
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<edge>[] lessMap = new ArrayList[group + 1];
int[] degree = new int[group + 1];
for(int i = 1;i <= group;i++)
lessMap[i] = new ArrayList<edge>();
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));
}
}
运行结果：
3 3
2
3
1
Yes