My approach:
According to the problem we have to minimize the cost to repair the lib and the roads. So what I did was if the cost of repairing the lib is <= cost of repairing the roads then I just simply return (numberOfCities * costOfRepairingLib). Otherwise I
count the no of connected components and the no of roads to be repaired then I calculated the cost and return it.
And I'm unable to pass 4, 5, 6, 8, 9 and 10 test cases and the test cases are so huge that I can't even debug. Please see where I did the mistake.
The logic feels fine to me but its failing for large test cases even I change every data type to long. I'm really stuck on this.
class Solution {
// Complete the roadsAndLibraries function below.
static long roadsAndLibraries(long n, long c_lib, long c_road, long[][] cities) {
if(c_lib <= c_road || c_road == 0)
return c_lib * n;
long[,] adjacentMatrix = new long[n, n];
Stack<long> stack = new Stack<long>();
Dictionary<long, bool> notVisited = new Dictionary<long, bool>();
Dictionary<long, bool> visited = new Dictionary<long, bool>();
for(long i = 1; i <= n; i++){
notVisited[i] = false;
}
foreach(var city in cities){
adjacentMatrix[city[0] - 1,city[1] -1] = 1;
adjacentMatrix[city[1] - 1,city[0] - 1] = 1;
}
long noOfCycles = 0;
long noOfRoads = 0;
while(notVisited.Count > 0){
stack.Push(notVisited.ElementAt(0).Key);
visited.Add(stack.Peek(), true);
notVisited.Remove(notVisited.ElementAt(0).Key);
noOfCycles++;
while(stack.Count > 0){
long top = stack.Pop();
for(long i = 0; i < n; i++){
if(adjacentMatrix[top - 1, i] == 1 && !visited.ContainsKey(i + 1)){
visited.Add(i + 1, true);
noOfRoads++;
stack.Push(i + 1);
notVisited.Remove(i + 1);
}
}
}
}
return (noOfCycles * c_lib) + (noOfRoads * c_road);
}
static void Main(string[] args) {
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
long q = Convert.ToInt64(Console.ReadLine());
for (long qItr = 0; qItr < q; qItr++) {
string[] nmC_libC_road = Console.ReadLine().Split(' ');
long n = Convert.ToInt64(nmC_libC_road[0]);
long m = Convert.ToInt64(nmC_libC_road[1]);
long c_lib = Convert.ToInt64(nmC_libC_road[2]);
long c_road = Convert.ToInt64(nmC_libC_road[3]);
long[][] cities = new long[m][];
for (long i = 0; i < m; i++) {
cities[i] = Array.ConvertAll(Console.ReadLine().Split(' '), citiesTemp => Convert.ToInt64(citiesTemp));
}
long result = roadsAndLibraries(n, c_lib, c_road, cities);
textWriter.WriteLine(result);
}
textWriter.Flush();
textWriter.Close();
}
}
