684.redundant-connection.md

684. Redundant Connection

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

Union Find

TODO:

DFS (Not Optimal)

We iterate every edge and try to append that edge to the graph (graph is empty at the beginning) to see if there is a cycle, if yes then it's redundant edge.

// At the beginning
1   3

2

// Append [1, 2] and run dfs(1, 2)
1   3
|
2

// Append [1, 3] and run dfs(1, 3)
1 - 3
| 
2

// ... so on

fun findRedundantConnection(edges: Array<IntArray>): IntArray {
    val graph = HashMap<Int, HashSet<Int>>()
    for (edge in edges) {
        val u = edge[0]
        val v = edge[1]
        if (dfs(graph, u, v, hashSetOf<Int>())) return edge

        if (!graph.containsKey(u)) graph[u] = hashSetOf<Int>()
        if (!graph.containsKey(v)) graph[v] = hashSetOf<Int>()
        graph[u]!!.add(v)
        graph[v]!!.add(u)
    }
    return edges[0]
}

private fun dfs(graph: HashMap<Int, HashSet<Int>>, source: Int, destination: Int, visited: HashSet<Int>): Boolean {
    if (source == destination) return true
    if (visited.contains(source)) return false
    visited.add(source)
    graph[source]?.forEach { adj ->
        if (dfs(graph, adj, destination, visited)) return true
    }
    return false
}

• Time Complexity: O(n^2), where n the number of vertices and edges.
• Space Complexity: O(n).