Articulation Points (or Cut Vertices) in a Graph

using System;
using System.Collections.Generic;

class Program {
    // A recursive function to traverse the graph without
    // considering the ith vertex and its associated edges
    static void Dfs(List<int>[] adj, int V, int[] vis,
                    int i, int curr)
    {
        vis[curr] = 1;
        foreach(var x in adj[curr])
        {
            if (x != i) {
                if (vis[x] == 0) {
                    Dfs(adj, V, vis, i, x);
                }
            }
        }
    }

    // Function to find Articulation Points in the graph
    static void AP(List<int>[] adj, int V)
    {
        // Iterating over all the vertices and for each
        // vertex i remove the vertex and check whether the
        // graph remains connected.
        for (int i = 1; i <= V; i++) {
            // To keep track of number of components of
            // graph
            int components = 0;

            // To keep track of visited vertices
            int[] vis = new int[V + 1];

            // Iterating over the graph after removing
            // vertex i and its associated edges
            for (int j = 1; j <= V; j++) {
                if (j != i) {
                    // If the jth vertex is not visited it
                    // will form a new component.
                    if (vis[j] == 0) {
                        // Increasing the number of
                        // components.
                        components++;

                        // dfs call for the jth vertex
                        Dfs(adj, V, vis, i, j);
                    }
                }
            }

            // If the number of components is more than 1
            // after removing the ith vertex, then vertex i
            // is an articulation point.
            if (components > 1) {
                Console.WriteLine(i);
            }
        }
    }

    // Utility function to add an edge
    static void AddEdge(List<int>[] adj, int u, int v)
    {
        adj[u].Add(v);
        adj[v].Add(u);
    }

    // Driver Code
    static void Main()
    {
        // Create graphs given in above diagrams
        Console.WriteLine(
            "Articulation points in the graph:");
        int V = 5;
        List<int>[] adj1 = new List<int>[ V + 1 ];
        for (int i = 0; i <= V; i++) {
            adj1[i] = new List<int>();
        }

        AddEdge(adj1, 1, 2);
        AddEdge(adj1, 2, 3);
        AddEdge(adj1, 1, 3);
        AddEdge(adj1, 3, 4);
        AddEdge(adj1, 4, 5);
        AP(adj1, V);
    }
}

// A C# program to find articulation
// points in an undirected graph
using System;
using System.Collections.Generic;

// This class represents an undirected graph
// using adjacency list representation
public class Graph {
    private int V; // No. of vertices

    // Array of lists for Adjacency List Representation
    private List<int>[] adj;
    int time = 0;
    static readonly int NIL = -1;

    // Constructor
    Graph(int v)
    {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new List<int>();
    }

    // Function to add an edge into the graph
    void addEdge(int v, int w)
    {
        adj[v].Add(w); // Add w to v's list.
        adj[w].Add(v); // Add v to w's list
    }

    // A recursive function that find articulation points using DFS
    // u --> The vertex to be visited next
    // visited[] --> keeps track of visited vertices
    // disc[] --> Stores discovery times of visited vertices
    // parent[] --> Stores parent vertices in DFS tree
    // ap[] --> Store articulation points
    void APUtil(int u, bool[] visited, int[] disc,
                int[] low, int[] parent, bool[] ap)
    {

        // Count of children in DFS Tree
        int children = 0;

        // Mark the current node as visited
        visited[u] = true;

        // Initialize discovery time and low value
        disc[u] = low[u] = ++time;

        // Go through all vertices adjacent to this
        foreach(int i in adj[u])
        {
            int v = i; // v is current adjacent of u

            // If v is not visited yet, then make it a child of u
            // in DFS tree and recur for it
            if (!visited[v]) {
                children++;
                parent[v] = u;
                APUtil(v, visited, disc, low, parent, ap);

                // Check if the subtree rooted with v has
                // a connection to one of the ancestors of u
                low[u] = Math.Min(low[u], low[v]);

                // u is an articulation point in following cases

                // (1) u is root of DFS tree and has two or more children.
                if (parent[u] == NIL && children > 1)
                    ap[u] = true;

                // (2) If u is not root and low value of one of its child
                // is more than discovery value of u.
                if (parent[u] != NIL && low[v] >= disc[u])
                    ap[u] = true;
            }

            // Update low value of u for parent function calls.
            else if (v != parent[u])
                low[u] = Math.Min(low[u], disc[v]);
        }
    }

    // The function to do DFS traversal.
    // It uses recursive function APUtil()
    void AP()
    {
        // Mark all the vertices as not visited
        bool[] visited = new bool[V];
        int[] disc = new int[V];
        int[] low = new int[V];
        int[] parent = new int[V];
        bool[] ap = new bool[V]; // To store articulation points

        // Initialize parent and visited, and
        // ap(articulation point) arrays
        for (int i = 0; i < V; i++) {
            parent[i] = NIL;
            visited[i] = false;
            ap[i] = false;
        }

        // Call the recursive helper function to find articulation
        // points in DFS tree rooted with vertex 'i'
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                APUtil(i, visited, disc, low, parent, ap);

        // Now ap[] contains articulation points, print them
        for (int i = 0; i < V; i++)
            if (ap[i] == true)
                Console.Write(i + " ");
    }

    // Driver method
    public static void Main(String[] args)
    {
        // Create graphs given in above diagrams
        Console.WriteLine("Articulation points in first graph ");
        Graph g1 = new Graph(5);
        g1.addEdge(1, 0);
        g1.addEdge(0, 2);
        g1.addEdge(2, 1);
        g1.addEdge(0, 3);
        g1.addEdge(3, 4);
        g1.AP();
        Console.WriteLine();

        Console.WriteLine("Articulation points in Second graph");
        Graph g2 = new Graph(4);
        g2.addEdge(0, 1);
        g2.addEdge(1, 2);
        g2.addEdge(2, 3);
        g2.AP();
        Console.WriteLine();

        Console.WriteLine("Articulation points in Third graph ");
        Graph g3 = new Graph(7);
        g3.addEdge(0, 1);
        g3.addEdge(1, 2);
        g3.addEdge(2, 0);
        g3.addEdge(1, 3);
        g3.addEdge(1, 4);
        g3.addEdge(1, 6);
        g3.addEdge(3, 5);
        g3.addEdge(4, 5);
        g3.AP();
    }
}

// This code is contributed by PrinciRaj1992