We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Time limit exceeded using c#, i dont know why.
I using Union Find,
public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<int>> cities)
{
var f = Enumerable.Range(0, n).ToArray();
List<List<int>> adjCities = cities.Select(x =>
{
x[0]--;
x[1]--;
return x;
}).ToList();
foreach (var city in adjCities)
{
var city1 = city[0];
var city2 = city[1];
merge(f, city1, city2);
}
var allGroupSize = GetAllGroupSize(f);
var minCost = allGroupSize.Select(x => CostMin(c_lib, c_road, x)).Sum();
return minCost;
}
private static int getf(int[] f, int v)
{
if (f[v] == v)
{
return v;
}
f[v] = getf(f, f[v]);
return f[v];
}
private static void merge(int[] f, int v, int u)
{
var t1 = getf(f, v);
var t2 = getf(f, u);
if (t1 != t2)
{
f[t2] = t1;
}
}
private static List<int> GetAllGroupSize(int[] f)
{
List<int> result = new List<int>();
List<int> leaders = GetLeader(f);
for (int i = 0; i < leaders.Count; i++)
{
int groupCount = GetGroupSize(f, leaders[i]);
result.Add(groupCount);
}
return result;
}
private static List<int> GetLeader(int[] f)
{
List<int> leaders = new List<int>();
for (int i = 0; i < f.Length; i++)
{
if (f[i] == i)
{
leaders.Add(i);
}
}
return leaders;
}
private static int GetGroupSize(int[] f, int v)
{
int groupSize = 0;
Stack<int> stack = new Stack<int>();
stack.Push(v);
while (stack.Count > 0)
{
int current = stack.Pop();
groupSize++;
for (int i = 0; i < f.Length; i++)
{
if (f[i] == current && i != current)
{
stack.Push(i);
f[i] = v; // Mark the city as visited to avoid revisiting it
}
}
}
return groupSize;
}
private static long CostMin(int c_lib, int c_road, int citiesCount)
{
// all lib
long allLibCost = c_lib * citiesCount;
//vs
// road with one lib
long roadWithLibCost = (citiesCount - 1) * c_road + c_lib * 1;
return Math.Min(allLibCost, roadWithLibCost);
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Roads and Libraries
You are viewing a single comment's thread. Return to all comments →
Time limit exceeded using c#, i dont know why. I using Union Find,