Find Bridges in a Tree
Given a connected undirected graph that is a tree, find all its bridges. A bridge is an edge whose removal increases the number of connected components of the graph. Since the input is guaranteed to be a tree, removing any edge will disconnect it.
Input
The first line contains an integer N, the number of nodes (vertices). The next N-1 lines each contain two integers u and v, representing an undirected edge between node u and node v. Nodes are numbered from 1 to N.
Output
Print the N-1 bridge edges. Each line should contain two space-separated integers representing the endpoints of a bridge. The smaller endpoint should be printed first. Print the bridges in lexicographical order.
Constraints
2 <= N <= 100000. The graph is guaranteed to be a tree.
Example 1
4 1 2 2 3 2 4
1 2 2 3 2 4
Edges (1,2), (2,3), (2,4) are printed in lexicographical order.
Example 2
5 1 2 1 3 1 4 1 5
1 2 1 3 1 4 1 5
A star graph. All edges originate from node 1.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 1 2 2 3 2 4
5 1 2 1 3 1 4 1 5