-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
65 lines (63 loc) · 1.78 KB
/
Solution.cs
File metadata and controls
65 lines (63 loc) · 1.78 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class Solution
{
public int[] FindRedundantConnection(int[][] edges)
{
// Build graph
Dictionary<int, HashSet<int>> graph = [];
int n = 0, k = edges.Length;
foreach (var edge in edges)
{
int u = edge[0];
int v = edge[1];
if (!graph.ContainsKey(u))
{
graph[u] = [];
}
if (!graph.ContainsKey(v))
{
graph[v] = [];
}
graph[u].Add(v);
graph[v].Add(u);
n = Math.Max(n, Math.Max(u, v));
}
for (int i = k - 1; i >= 0; i--)
{
// remove edge from graph
int u = edges[i][0];
int v = edges[i][1];
graph[u].Remove(v);
graph[v].Remove(u);
if (!HasCycle(graph, n + 1))
{
return edges[i];
}
graph[u].Add(v);
graph[v].Add(u);
}
return [];
}
private bool HasCycle(Dictionary<int, HashSet<int>> graph, int n)
{
bool[] visited = new bool[n];
for (int i = 1; i < n; i++)
{
if (visited[i]) continue;
Queue<(int, int)> queue = [];
queue.Enqueue((i, -1));
visited[i] = true;
while (queue.Count > 0)
{
var (curr, parent) = queue.Dequeue();
foreach (var next in graph.GetValueOrDefault(curr, []))
{
if (visited[next] && next != parent) return true;
if (visited[next] || next == parent) continue;
visited[next] = true;
queue.Enqueue((next, curr));
}
}
}
return false;
}
}