-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
63 lines (60 loc) · 1.67 KB
/
Solution.cs
File metadata and controls
63 lines (60 loc) · 1.67 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
public class Solution
{
public int[] MaxTargetNodes(int[][] edges1, int[][] edges2, int k)
{
int n = edges1.Length + 1;
int m = edges2.Length + 1;
List<int>[] adj1 = new List<int>[n];
List<int>[] adj2 = new List<int>[m];
for (int i = 0; i < n; i++) adj1[i] = [];
for (int i = 0; i < m; i++) adj2[i] = [];
foreach (int[] e in edges1)
{
int u = e[0], v = e[1];
adj1[u].Add(v);
adj1[v].Add(u);
}
foreach (int[] e in edges2)
{
int u = e[0], v = e[1];
adj2[u].Add(v);
adj2[v].Add(u);
}
int[] ret = new int[n];
int maxTarget = 0;
for (int i = 0; i < m; i++)
{
maxTarget = Math.Max(maxTarget, CountTarget(i, adj2, k - 1));
}
for (int i = 0; i < n; i++)
{
ret[i] = CountTarget(i, adj1, k) + maxTarget;
}
return ret;
}
int CountTarget(int node, List<int>[] adj, int k)
{
int n = adj.Length;
bool[] visited = new bool[n];
Queue<int> queue = [];
queue.Enqueue(node);
visited[node] = true;
int count = 0;
while (queue.Count > 0 && k >= 0)
{
count += queue.Count;
for (int i = queue.Count; i > 0; i--)
{
int curr = queue.Dequeue();
foreach (int next in adj[curr])
{
if (visited[next]) continue;
visited[next] = true;
queue.Enqueue(next);
}
}
k--;
}
return count;
}
}