Problems

Maximum edges in a DAG

Problem Statement: Find the maximum number of edges in a DAG

Approach:
Maximum edges in a directed graph is \(V^2\). Maximum edges is a DAG is \(\frac{V(V-1)}{2}\)

---

Cut Vertex

Problem Statement: Find the cut vertices in a graph.
A vertex if removed splits the undirected graph into two connected components is called a cut vertex.

Approach: Let

• disc[u]: Discovery time of vertex u or order in DFS traversal
• low[u]: Lowest discovery time reachable from u or its descendants. The earliest visited node reachable from u or any of its descendants (through any path, including back edges).

low[u] helps to detect whether the subtree rooted at v can connect back to any of u's ancestors. If not, removing u will disconnect the graph — making u a cut vertex.

A vertex u is cut vertex if:

1. u is root of DFS and has 2 or more children
2. u is not root and there is a child v such that low[v] >= disc[u]. This means the subtree rooted at v cannot reach an ancestor of u without passing through u.

fun findCutVertices(graph: Graph) {
    val cutVertices = mutableListOf<Int>()
    val disc = MutableList(graph.V) { -1 }
    val low = MutableList(graph.V) { - 1}
    val parent = MutableList(graph.V) { -1 }
    val visited = BooleanArray(graph.V) { false }
    var t = 0

    fun dfs(u: Int) {
        visited[u] = true
        disc[u] = t
        low[u] = t
        t++
        var child = 0

        for(v in graph.adjList[u]) {
            if(!visited[v]) {
                parent[v] = u
                dfs(v)
                child++
                low[u] = minOf(low[u], low[v])
                if(parent[u] == -1 && child > 1) {
                    cutVertices.add(u)
                } else if(parent[u] != -1 and low[v] >= disc[u]) {
                    cutvertices.add(u)
                }
            } else if(v != parent[u]) {
                low[u] = min(low[u], disc[v])
            }
        }
    }

    for (u in 0 until graph.V) {
        if (!visited.contains(u)) {
            parent[u] = null
            dfs(u)
        }
    }
}

---

Cut Edges/Bridges

Problem Statement: Find bridges in a graph

Approach:
An edge uv is called a bridge if G - uv is disconnected. Edge (u,v) cannot be a bridge if it is part of a cycle, else it is a bridge. We can detect cycles using DFS. (u, v) is a bridge iff none of v or v's children have a back edge to u or any of u's ancestors.

fun findBridges(graph: Graph) {
    val bridges  = mutableListOf<Pair<Int, Int>>()
    val disc = MutableList(graph.V) { -1 }
    val low = MutableList(graph.V) { - 1}
    val parent = MutableList(graph.V) { -1 }
    val visited = BooleanArray(graph.V) { false }
    var t = 0

    fun dfs(u: Int) {
        visited[u] = true
        disc[u] = t
        low[u] = t
        t++
        var child = 0

        for(v in graph.adjList[u]) {
            if(u == v) continue 
            if(!visited[v]) {
                parent[v] = u
                dfs(v)
                child++
                low[u] = minOf(low[u], low[v])

                if(low[v] >= disc[u]) {
                    bridges.add(Pair(u, v))
                }
            } else if(v != parent[u]) {
                low[u] = min(low[u], disc[v])
            }
        }
    }

    for (u in 0 until graph.V) {
        if (!visited.contains(u)) {
            parent[u] = null
            dfs(u)
        }
    }

}

---

Euler Circuits

Problem Statement: Find if a graph contains an euler circuit

Approach:
Terminology:

• Eulerian Tour: A path that contains all edges without repetition.
• Eulerian circuit: Eulerian tour that starts and ends with the same vertex.

A connected undirected graph is Eulerian iff every vertex has even degree, or exactly 2 vertices with odd degree.
A directed graph is Eulerian if it is strongly connected, and every vertex has an equal in and out degree.

Refer code

---

Strongly Connected Components

Problem Statement: Check is the graph is strongly connected

Approach:
In a directed graph u and v are strongly connected iff there exists a path from u to v and v to u. If u is strongly connected to v, and v is strongly connected to x then u is strongly connected to x.

---

Num of Connected Components

Problem Statement: Find the num of connected components in a graph

Approach: Initially, all nodes are not visited. Run DFS on all nodes that are not visited. Whenever we start a new DFS traversal it's a new component.

fun dfs(graph: Graph, visited: BooleanArray, s: Int)

fun numComponents(graph: Graph) {
    val visited = BooleanArray{graph.V}
    var count = 0

    for(u in 0 until graph.V) {
        if(!visited[u]) {
            count++
            dfs(graph, visited, u)
        }
    }
}

---

Detect cycle in undirected

Problem Statement: Given an undirected graph, check if it contains a cycle.

Approach:
An undirected graph is acyclic iff there are no back edges in a DFS traversal.

---

Detect cycle in directed

Problem Statement: Given a directed graph check if it contains a cycle

Approach:
Unlike directed graph, we don't get a back edge just because we see an already visited node. A directed graph has a cycle only if in a dfs path we start at a node, and we come back to that node.

fun hasCycle(graph: Graph, visited: BooleanArray, u: Int) {
    visited[u] = true
    inPath[u] = true

    graph.adjList[u].forEach { v ->
        if (!visited[v]) {
            if(hasCycle(graph, visited, v))
                return true
        } else if (inPath[v]) {
            return true
        }
    }

    inPath[u] = false
    return false
}

fun detectCycle(graph: Graph): Boolean {
    val visited = BooleanArray(graph.V)
    val inPath = BooleanArray(graph.V)

    for (u in 0 until graph.V) {
        if (!visited[u]) {
            if (hasCycle(graph, visited, u)) return true
        }
    }
    return false
}

graph TD

    0((0)) --> 1
    1 --> 2
    2 --> 3
    2 --> 4

    10 --> 0
    10 --> 11
    10 --> 12
    0 --> 12

There is no cycle is this graph. If we use the same algorithm as directed graph we will detect a wrong cycle.

---

LCA of a DAG

Problem Statement: Given 2 vertices u, v find the lowest common ancestor of u and v. The LCA of u and v is an ancestor that has no descendants that are also ancestors.

Approach:

1. Topological sort on DAG
2. Get ancestors of node u & v
3. The last node that is the ancestor in topological order is the LCA of 2 nodes

fun lca(graph: Graph, u: Int, v: Int) {
    val topologicalOrder = topologicalSort()

    // Get ancestors
    val ancestors = MutableList(graph.V) { BitSet(graph.V) }
    topologicalOrder.forEach { node ->
        graph.adjList[node].forEach {
            ancestors[it].or(ancestors[node])
            ancestors[it].set(node)
        }
    }

    topologicalOrder.reversed().forEach { node -> 
        if(ancestors[u].get(node) && ancestors[v].get(node))
            return node
    }

    return -1
}

---

Shortest Ancestral Path

Problem Statement: Given two nodes, find the shortest ancestral path between the nodes.

Approach:
If x is a common ancestor. An ancestral path between u and v is the shortest path from x to u and x to v.
We are typically looking for a common ancestor x that minimizes the sum of the shortest paths from x to u and from x to v.

---

Hamiltonian Path

Problem Statement:

Approach:

---

Travelling Salesman

Problem Statement:

Approach:

---

Bipartite Matching (Hungarian Algo)

Problem Statement:

Approach:

---

Graph Coloring

Problem Statement:

Approach: