Help in Graph question
network consists of N nodes (numbered 1 through N) and M bidirectional connections between pairs of these nodes. A robust network is a network that contains a cycle. Shutting down a node means removing that node (and all direct connections it is part of) from the network.
You may shut down at most one node. If the network was robust before it was shut down and is not robust afterwards, this node is called the point of failure.
Is the initial network robust? If it is robust, does it have a point of failure? If it does, find the point of failure with the smallest number.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M.
Each of the following M lines contains two space-separated integers u and v denoting that nodes u and v are directly connected.
Output
For each test case, print a single line containing one integer ― the smallest number of a point of failure, or −1 if the network does not have a point of failure.
Constraints
1≤T≤10
1≤N≤105
0≤M≤105
1≤u,v≤N
Subtasks
Subtask #1 (10 points):
N≤100
N−1≤M≤N+1
the given graph is connected
Subtask #2 (10 points): 1≤N≤100
Subtask #3 (30 points): 1≤N≤1,000
Subtask #4 (50 points): original constraints
Example Input
5
5 5
5 1
5 2
1 2
2 3
2 4
5 6
4 5
4 1
4 2
4 3
5 1
5 2
5 5
3 4
3 5
3 1
3 2
4 2
4 1
3 4
6 6
1 2
2 3
3 1
4 5
5 6
6 4
Example Output
1
4
2
-1
-1
You may shut down at most one node. If the network was robust before it was shut down and is not robust afterwards, this node is called the point of failure.
Is the initial network robust? If it is robust, does it have a point of failure? If it does, find the point of failure with the smallest number.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M.
Each of the following M lines contains two space-separated integers u and v denoting that nodes u and v are directly connected.
Output
For each test case, print a single line containing one integer ― the smallest number of a point of failure, or −1 if the network does not have a point of failure.
Constraints
1≤T≤10
1≤N≤105
0≤M≤105
1≤u,v≤N
Subtasks
Subtask #1 (10 points):
N≤100
N−1≤M≤N+1
the given graph is connected
Subtask #2 (10 points): 1≤N≤100
Subtask #3 (30 points): 1≤N≤1,000
Subtask #4 (50 points): original constraints
Example Input
5
5 5
5 1
5 2
1 2
2 3
2 4
5 6
4 5
4 1
4 2
4 3
5 1
5 2
5 5
3 4
3 5
3 1
3 2
4 2
4 1
3 4
6 6
1 2
2 3
3 1
4 5
5 6
6 4
Example Output
1
4
2
-1
-1
Is there a question? I scanned but did not see it, it just looks like a copy of a textbook problem.
It's another codechef problem:
https://www.codechef.com/NOV19B/problems/FAILURE
Notacoder, the best thing you can do is to stop doing codechef problems. They are badly formed and test your math ability more than your coding skills.
That said, finding cycles is easy. Do a depth first traversal of the graph. At each node, set a flag on the node before descending and clear the flag when you come back up. If you ever descend into a node that has the flag set, you've found a cycle.
You can break the cycle by removing the edge that forms it, but what if there are other cycles? And how will you remove the smallest numbered edge?
https://www.codechef.com/NOV19B/problems/FAILURE
Notacoder, the best thing you can do is to stop doing codechef problems. They are badly formed and test your math ability more than your coding skills.
That said, finding cycles is easy. Do a depth first traversal of the graph. At each node, set a flag on the node before descending and clear the flag when you come back up. If you ever descend into a node that has the flag set, you've found a cycle.
You can break the cycle by removing the edge that forms it, but what if there are other cycles? And how will you remove the smallest numbered edge?
this has a lot of the hallmarks of a no-graph graph problem. I suspect it can be done with a few vectors, sorted... not 100% sure of that, but adding 2 & 2 (all the CC problems have a high speed gimmick to find, and this kind of graph problem leans toward arrays).
Topic archived. No new replies allowed.