Vertex and Edge Cut Algorithms
=============================

In graph theory, cut vertices (articulation points) and cut edges (bridges) play a crucial role in analyzing network connectivity. A cut vertex is a node whose removal increases the number of connected components, while a cut edge is a link whose removal does the same.

To find these points and edges, various algorithms exist – the most famous being Tarjan's algorithm. This algorithm uses DFS (Depth-First Search) and two key properties for each vertex: ``index`` (discovery time) and ``low_link`` (the lowest index reachable from that vertex through DFS edges).

.. code:: c

   typedef struct {
       int index; // vertex number
       int low_link; // vertex's lowest root
       bool onStack; // is on the stack?
   } TarjanNode;

.. figure:: images/tarjan.png

Applications of these algorithms include identifying critical nodes in computer networks, analyzing social network vulnerabilities, and detecting communities in complex systems.

Finding Bridge Edges
--------------------
To find bridge edges, we first run the DFS algorithm on the graph. While running the DFS algorithm, for each vertex u, we maintain a value ``dp[u]`` which equals the lowest height reachable via back edges from vertices in the subtree of u. The value ``dp[u]`` for each vertex is calculated as the minimum value among its children's values and the height of its own back edges.

An edge between vertex v and its parent ``parent[v]`` is a bridge if and only if the value of ``dp[v]`` is not less than the height of v. This means there is no edge in the subtree of v that connects to a vertex above v.

The runtime of this algorithm is O(n + m), where n represents the number of vertices and m represents the number of edges.

.. code-block:: cpp

    const int maxn = 1e6 + 10;
    
    bool mark[maxn], is[maxn];
    int dp[maxn], height[maxn];
    pair<int, int> edge[maxn];
    vector<pair<int, int> > adj[maxn];
    
    void dfs(int v,int parent,int index){
        dp[v] = height[v];
        mark[v] = true;
        for(int i = 0; i < adj[v].size(); i++){
            int u = adj[v][i].first;
            int ind = adj[v][i].second;
            if(!mark[u]){
                height[u] = height[v] + 1;
                dfs(u, v, ind);
                dp[v] = min(dp[v], dp[u]);
            }
            else{
                if(u != parent){
                    dp[v] = min(dp[v], height[u]);
                }
            }
        }
        if(v != 1 && dp[v] == height[v])
            is[index] = true;
        return;
    }
    
    int main(){
        int n, m;
        cin >> n >> m;
        for(int i = 0; i < m; i++){
            int u, v;
            cin >> u >> v;
            edge[i] = {u, v};
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }
        dfs(1, 0, 0);
        for(int i = 0; i < m; i++)
            if(is[i])
                cout << edge[i].first << " " << edge[i].second << endl;
        return 0;
    }

Finding Articulation Points
----------------------------
In this section, similar to finding bridges, we compute the dp[u] value using the same definition for vertex u. A vertex is an articulation point if removing it splits the graph into more than one component. Therefore, in the DFS tree we constructed, a vertex *v* is an articulation point if the dp value of all its children is greater than the height (depth) of vertex *v*, meaning no back edge exists to a higher ancestor. Note that the root is an articulation point if its degree is not one.

The time complexity of this algorithm is also O(n + m).

.. code-block:: cpp

    const int maxn = 1e6 + 10;
    
    bool mark[maxn], is[maxn];
    int dp[maxn], height[maxn];
    vector<int> adj[maxn];
    
    void dfs(int v,int parent){
        dp[v] = height[v];
        mark[v] = true;
        int num = 0;
        for(int i = 0; i < adj[v].size(); i++){
            int u = adj[v][i];
            if(!mark[u]){
                height[u] = height[v] + 1;
                dfs(u, v);
                if(v != 1 && dp[u] >= height[v])
                    is[v] = true;
                dp[v] = min(dp[v], dp[u]);
                num++;
            }
            else if(u != parent)
                dp[v] =min(dp[v], height[u]);
        }
        if(v == 1 && num > 1)
            is[v] = true;
        return;
    }
    
    int main(){
        int n, m;
        cin >> n >> m;
        for(int i = 0; i < m; i++){
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dfs(1, 0);
        for(int u = 1; u <= n; u++)
            if(is[u])
                cout << u << " ";
        return 0;
    }