EC_P - Critical Edges
This time I will not bore you with a long and boring sentence. Give a connected graph, you must find all the edges that are critical, in other words you must find the edges which when removed divide the graph.
Input
The first line contains a integer NC (1 ≤ NC ≤ 200), the number of test cases. Then follow NC test cases.
Each case begins with two integers N (1 ≤ N ≤ 700) and M (N-1 ≤ M ≤ N * (N-1) / 2), the number of nodes and the number of edges respectively. Then follow M lines, each with a pair of integers a b (1 ≤ a, b ≤ N) indicate that between the node a and the node b there is a edge.
Output
For each test case print the list of ways to protect the following format:
Caso # <n>
<t>
<x1> <y2>
<x2> <y2>
...
<xt> <yt>
Where n is the case number (starting from 1), t is the total of critical edges, list elements xi yi indicates, for each line, there is a critical edge between the node xi and node yi (1 ≤ xi <yi ≤ N). In addition, the list should be sorted in no-decreasing order first by xi and then by yi. Also xi < yi must hold.
If there isn't any critical edge print: "Sin bloqueos" (quotes for clarity).
Example
Input:3 5 4 1 2 4 2 2 3 4 5 5 5 1 2 1 3 3 2 3 4 5 4 4 6 1 3 1 4 2 1 3 2 4 2 4 3Output:Caso #1 4 1 2 2 3 2 4 4 5 Caso #2 2 3 4 4 5 Caso #3 Sin bloqueos
hide comments
|
dineshbarri:
2021-04-05 10:26:34
Need not check for multiple edges. Just add this step instead inserting directly --> bridge.pb({min(u,it),max(u,it)}); |
|
ashutosh_coder:
2021-02-01 07:29:18
not take another case like if there is n-1 edges then simply print edges in sorted order
|
|
nadstratosfer:
2021-01-06 02:17:22
Impossible to AC with raw Python in 0.1s and PyPy is disabled for no reason; downvote. |
|
amit_as_king:
2020-07-09 09:54:19
showing TLE in JAVA even with fast IO Last edit: 2020-07-09 09:55:46 |
|
subhash2000:
2020-07-01 19:02:01
Showing TLE in java while code is O(V+E). Can anyone tell better approach in java |
|
abu_rifat:
2020-04-11 20:24:06
AC in 1 Go. :) |
|
luvkumbi:
2020-02-20 19:40:19
Cool....learned to detect bridges in a graph....while inserting bridges in final ans.....see that xi<yi and also print edges in lexographically increasing order. |
|
jerry_san:
2019-12-08 20:30:16
I am getting runtime error in this question. can someone help me with this |
|
parsae:
2019-10-30 08:53:23
can anyone give a test case |
|
scolar_fuad:
2019-09-25 15:00:37
(simpleBridege point problem )
|
Added by: | Eddy Cael |
Date: | 2013-10-31 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C-CLANG C C++ 4.3.2 CPP CPP14 CPP14-CLANG JAVA PYTHON PYTHON3 |