| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1066 | Shortest Path (I) |
|
| 1069 | Directed-graph (I) |
|
| 1072 | Topological Sort (I) |
|
Description
Given an undirected graph and a source vertex s, compute the minimum distance of each node from s. We may assume the label of s is always 0, and then the other nodes in the graph are labeled respectively by 1, 2, ..., n.
Input
The input format:
n, m := number of nodes, number of edges
x1 y1
x2 y2
...
xm ym := the m edges
For each case, the first line contains two integers n and m. Then m lines follow. Each line contains two integers x and y, denoting there is an edge between x and y. There is at most one edge between two nodes.
There are many cases in the input. Cases are separated by a blank line. Input will be terminated by EOF (End-Of-File).
Problem size :
1066: 1 <= n <= 15
1067: 1 <= n <= 200
1068: 1 <= n <= 1000
0 <= m <= n*(n-1)/2
Note that there are exactly n+1 nodes, including the source node 0.
For this problem, any algorithm with time complexity O(n2) is accepted.
You can download the testdata and test your program, we do not use the same data to test your program.
Output
The output format:
5 4 1 - 3 2 1 2 1 4 ... #
where the ith number is the min distance between node i with s (node 0) and "-" indicates such a node is unreachable from s, and "#" indicates end of each case.
.jpg)
For this case, the output is:
1 2 - 1 2 #
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Please write a program to find out that whether a directed graph has cycles.
Input
There are many cases in input.
The first line in the input contains three integers: n, m, representing the number of nodes in the graph and the number of edges in the graph.
The next m lines, each line contains 2 integers, u and v (1<= u, v <= n). That means there is an edge from u to v(v to u has no edge).
Input will be terminated by EOF (End-Of-File).
There has no node connected to itself!!
Problem size
1069: 1 <= n <= 10
1070: 1 <= n <= 100
1071: 1 <= n <= 1000
0 <= m <= n*(n-1)
Input 1: O(n!) can pass this
Input 2: O(n3) can pass this
Input 3: O(n2) can pass this
You can download the testdata and test your program, we do not use the same data to test your program.
Output
For each case, print YES if there has at least one cycle in the graph, otherwise, print NO.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
This problem is special judge.
To accerlelate judging, we will use offline judge.
You should test your program with this zip file(like lab):
140.114.86.238/DS/prob3.zip (windows)
prob3_Mac.zip
If you have confidence with your code, please sumbit your C or C++ code to this link:
140.114.86.238/DS/topo.php
Please write a program to implement topological sort.
Input
There are many cases in input.
The first line in the input contains three integers: n and m, representing the number of nodes in the graph, the number of edges in the graph.
The next m lines, each line contains 2 integers, u and v (1<= u, v <= n). That means there is an edge between u and v. There is at most one edge between two nodes.
Input will be terminated by EOF (End-Of-File).
1 <= n <= 100000
0 <= m <=500000
Input 1: O(n!) can pass this
Input 2: O(n2) can pass this
Input 3: O(n+m) can pass this
Output
For each case, output one line with the traversal order of DFS from the source.
We will test your program by special judge. So you can pass the testing data if you give valid topological order.