#C2611. Important Nodes in an Undirected Graph
Important Nodes in an Undirected Graph
Important Nodes in an Undirected Graph
Given an undirected graph \( G=(V,E) \) with \( n \) nodes and \( m \) edges, an important node (or articulation point) is defined as a vertex which, when removed along with all its incident edges, increases the number of connected components of the graph. Your task is to identify all such important nodes.
If there are no important nodes in the graph, output -1
. Otherwise, output the list of important nodes in ascending order.
Example:
Input: 7 6 1 2 2 3 3 4 4 5 5 6 6 7</p>Output: 2 3 4 5 6
Note: Use the Tarjan algorithm for finding articulation points, where the following condition is crucial: for a node \( u \) and a vertex \( v \) in one of its subtrees, if \( low[v] \geq disc[u] \) then \( u \) is an articulation point. For the root, it is an articulation point only if it has more than one child in the DFS tree.
inputFormat
The first line contains two integers \( n \) and \( m \), representing the number of nodes and edges respectively.
Each of the next \( m \) lines contains two space-separated integers \( u \) and \( v \) indicating that there is an undirected edge between node \( u \) and node \( v \).
Nodes are numbered from 1 to \( n \).
outputFormat
If there is at least one important node, print them in ascending order separated by a space on a single line. Otherwise, print -1
.
7 6
1 2
2 3
3 4
4 5
5 6
6 7
2 3 4 5 6
</p>