-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
77 lines (71 loc) · 2.09 KB
/
Solution.cs
File metadata and controls
77 lines (71 loc) · 2.09 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
66
67
68
69
70
71
72
73
74
75
76
77
public class Solution
{
public int LargestPathValue(string colors, int[][] edges)
{
int n = colors.Length;
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++)
{
graph[i] = [];
}
foreach (int[] edge in edges)
{
int u = edge[0], v = edge[1];
graph[u].Add(v);
}
if (HasCycle(graph, n)) return -1;
int ret = 1;
int[] dp = new int[n];
HashSet<char> set = [.. colors];
foreach (char c in set)
{
Array.Clear(dp);
bool[] visited = new bool[n];
PriorityQueue<int, int> pq = new();
for (int i = 0; i < n; i++)
{
if (visited[i]) continue;
dp[i] = colors[i] == c ? 1 : 0;
pq.Enqueue(i, -dp[i]);
while (pq.Count > 0)
{
int curr = pq.Dequeue();
foreach (int next in graph[curr])
{
visited[next] = true;
int w = colors[next] == c ? 1 : 0;
if (dp[curr] + w > dp[next])
{
dp[next] = dp[curr] + w;
pq.Enqueue(next, -dp[next]);
}
}
}
}
ret = Math.Max(ret, dp.Max());
}
return ret;
}
bool HasCycle(List<int>[] graph, int n)
{
bool[] visited = new bool[n];
bool[] colored = new bool[n];
for (int i = 0; i < n; i++)
{
if (!visited[i] && DFS(i, graph, visited, colored)) return true;
}
return false;
}
bool DFS(int u, List<int>[] graph, bool[] visited, bool[] colored)
{
visited[u] = true;
colored[u] = true;
foreach (int v in graph[u])
{
if (!visited[v] && DFS(v, graph, visited, colored)) return true;
if (colored[v]) return true;
}
colored[u] = false;
return false;
}
}