#C5923. Critical Connection Points
Critical Connection Points
Critical Connection Points
You are given an undirected graph with N nodes and M edges. The graph is described by M pairs of integers, each representing an edge between two nodes. A Critical Connection Point (CCP) is defined as an articulation point in the graph, i.e., a vertex whose removal increases the number of connected components.
Formally, let \(G = (V, E)\) be an undirected graph. A vertex \(v \in V\) is an articulation point if and only if its removal (along with the removal of all edges incident to \(v\)) results in a graph with more connected components than the original graph.
Your task is to compute the number of Critical Connection Points in the given graph.
Note: Use the DFS based Tarjan's Algorithm to identify the articulation points. The key formula used in the algorithm is:
[ low[u] = \min (disc[u], \min_{v \in children(u)} low[v], \min_{v \text{ is a back edge from } u} disc[v]) ]
inputFormat
The first line contains two integers N and M, where N is the number of nodes and M is the number of edges.
The next 2*M integers represent M pairs, each pair consists of two integers U and V indicating an undirected edge between node U and node V.
Nodes are numbered from 1 to N.
outputFormat
Output a single integer which is the number of Critical Connection Points in the graph.
## sample6 7
1 2 2 3 3 1 1 4 4 5 5 6 6 4
2