The Ruler of HackerLand believes that every citizen of the country should have access to a library. Unfortunately, HackerLand was hit by a tornado that destroyed all of its libraries and obstructed its roads! As you are the greatest programmer of HackerLand, the ruler wants your help to repair the roads and build some new libraries efficiently.
HackerLand has n cities numbered from 1 to n. The cities are connected by bidirectional roads. A citizen has access to a library if:
- Their city contains a library.
- They can travel by road from their city to a city containing a library.
The cost of repairing any road is croad dollars, and the cost to build a library in any city is clib dollars.
You are given q queries, where each query consists of a map of HackerLand and value of clib and croad. For each query, find the minimum cost of making libraries accessible to all the citizens and print it on a new line.
The Ruler of HackerLand believes that every citizen of the country should have access to a library. Unfortunately, HackerLand was hit by a tornado that destroyed all of its libraries and obstructed its roads! As you are the greatest programmer of HackerLand, the ruler wants your help to repair the roads and build some new libraries efficiently.
HackerLand has n cities numbered from 1 to n. The cities are connected by bidirectional roads. A citizen has access to a library if:
- Their city contains a library.
- They can travel by road from their city to a city containing a library.
The cost of repairing any road is croad dollars, and the cost to build a library in any city is clib dollars.
You are given q queries, where each query consists of a map of HackerLand and value of clib and croad. For each query, find the minimum cost of making libraries accessible to all the citizens and print it on a new line.
The Ruler of HackerLand believes that every citizen of the country should have access to a library. Unfortunately, HackerLand was hit by a tornado that destroyed all of its libraries and obstructed its roads! As you are the greatest programmer of HackerLand, the ruler wants your help to repair the roads and build some new libraries efficiently.
HackerLand has n cities numbered from 1 to n. The cities are connected by bidirectional roads. A citizen has access to a library if:
- Their city contains a library.
- They can travel by road from their city to a city containing a library.
The cost of repairing any road is croad dollars, and the cost to build a library in any city is clib dollars.
You are given q queries, where each query consists of a map of HackerLand and value of clib and croad. For each query, find the minimum cost of making libraries accessible to all the citizens and print it on a new line.
HackerLand has n cities numbered from 1 to n. The cities are connected by bidirectional roads. A citizen has access to a library if:
The cost of repairing any road is croad dollars, and the cost to build a library in any city is clib dollars.
You are given q queries, where each query consists of a map of HackerLand and value of clib and croad. For each query, find the minimum cost of making libraries accessible to all the citizens and print it on a new line.
Input Format
The first line contains a single integer, q, denoting the number of queries. The subsequent lines describe each query in the following format:
The first line contains four space-separated integers describing the respective values of n(the number of cities), m(the number of roads), clib(the cost to build a library), and croad(the cost to repair a road). Each line iof the msubsequent lines contains two space-separated integers, ui and vi, describing a bidirectional road connecting cities uiand vi.
A citizen has access to a library if:
The cost of repairing any road is dollars, and the cost to build a library in any city is dollars.
You are given queries, where each query consists of a map of HackerLand and value of and. For each query, find the minimum cost of making libraries accessible to all the citizens and print it on a new line.
HackerLand has n cities numbered from 1 to n. The cities are connected by bidirectional roads. A citizen has access to a library if:
The cost of repairing any road is croad dollars, and the cost to build a library in any city is clib dollars.
You are given q queries, where each query consists of a map of HackerLand and value of clib and croad. For each query, find the minimum cost of making libraries accessible to all the citizens and print it on a new line.
Input Format
The first line contains a single integer, q, denoting the number of queries. The subsequent lines describe each query in the following format:
The first line contains four space-separated integers describing the respective values of n(the number of cities), m(the number of roads), clib(the cost to build a library), and croad(the cost to repair a road). Each line iof the msubsequent lines contains two space-separated integers, ui and vi, describing a bidirectional road connecting cities uiand vi.
class Program
{
static void Main(string[] args)
{
List<Int64>[] adj;
Int64 q = Convert.ToInt32(Console.ReadLine()); //Number of queries
Int64 costLib =0;
Int64 costStr =0;
List<Int64> result;
for (Int64 a0 = 0; a0 < q; a0++)
{
string[] tokens_n = Console.ReadLine().Split(' ');
Int64 n = Convert.ToInt32(tokens_n[0]); //Number of cities
Int64 m = Convert.ToInt32(tokens_n[1]); //Number of streets
Int64 x = Convert.ToInt64(tokens_n[2]); //Cost of library
Int64 y = Convert.ToInt64(tokens_n[3]); //Cost of street
adj = Graph(n);
costLib = x;
costStr = y;
for (Int64 a1 = 0; a1 < m; a1++)
{
string[] tokens_city_1 = Console.ReadLine().Split(' ');
Int64 city_1 = Convert.ToInt32(tokens_city_1[0]);
Int64 city_2 = Convert.ToInt32(tokens_city_1[1]);
AddEdge(city_1-1, city_2-1,adj);
}
if (x <= y)
{
Console.WriteLine(costLib * n);
}
else
{
result = DFS(n,adj);
Console.WriteLine(result[1] * costStr + result[0] * costLib);
}
}
}
static List<Int64>[] Graph(Int64 v)
{
Int64 Vertices = v;
List<Int64>[] adj = new List<Int64>[v];
for (Int64 i = 0; i < v; i++)
{
adj[i] = new List<Int64>();
}
return adj;
}
static void AddEdge(Int64 v, Int64 w, List<Int64>[] adj)
{
adj[v].Add(w);
}
static List<Int64> DFS(Int64 v, List<Int64>[] adj)
{
Int64 s = 0;
Int64 streetCounter = 0;
Int64 LibraryCounter = 1;
bool[] visited = new bool[v];
List<Int64> result = new List<Int64>();
Stack<Int64> stack = new Stack<Int64>();
visited[s] = true;
stack.Push(s);
while (stack.Count != 0)
{
s = stack.Pop();
foreach (Int64 i in adj[s])
{
if (!visited[i])
{
visited[i] = true;
stack.Push(i);
streetCounter++;
}
}
if (stack.Count == 0)
{
for (Int64 ii = 0; ii < v; ii++)
{
if (visited[ii] != true)
{
stack.Push(ii);
LibraryCounter++;
streetCounter--;
break;
}
}
}
}
result.Add(LibraryCounter);
result.Add(streetCounter);
return result;
}
class Program
{
static void Main(string[] args)
{
List<Int64>[] adj;
Int64 q = Convert.ToInt32(Console.ReadLine()); //Number of queries
Int64 costLib =0;
Int64 costStr =0;
List<Int64> result;
for (Int64 a0 = 0; a0 < q; a0++)
{
string[] tokens_n = Console.ReadLine().Split(' ');
Int64 n = Convert.ToInt32(tokens_n[0]); //Number of cities
Int64 m = Convert.ToInt32(tokens_n[1]); //Number of streets
Int64 x = Convert.ToInt64(tokens_n[2]); //Cost of library
Int64 y = Convert.ToInt64(tokens_n[3]); //Cost of street
adj = Graph(n);
costLib = x;
costStr = y;
for (Int64 a1 = 0; a1 < m; a1++)
{
string[] tokens_city_1 = Console.ReadLine().Split(' ');
Int64 city_1 = Convert.ToInt32(tokens_city_1[0]);
Int64 city_2 = Convert.ToInt32(tokens_city_1[1]);
AddEdge(city_1-1, city_2-1,adj);
}
if (x <= y)
{
Console.WriteLine(costLib * n);
}
else
{
result = DFS(n,adj);
Console.WriteLine(result[1] * costStr + result[0] * costLib);
}
}
}
static List<Int64>[] Graph(Int64 v)
{
Int64 Vertices = v;
List<Int64>[] adj = new List<Int64>[v];
for (Int64 i = 0; i < v; i++)
{
adj[i] = new List<Int64>();
}
return adj;
}
static void AddEdge(Int64 v, Int64 w, List<Int64>[] adj)
{
adj[v].Add(w);
}
static List<Int64> DFS(Int64 v, List<Int64>[] adj)
{
Int64 s = 0;
Int64 streetCounter = 0;
Int64 LibraryCounter = 1;
bool[] visited = new bool[v];
List<Int64> result = new List<Int64>();
Stack<Int64> stack = new Stack<Int64>();
visited[s] = true;
stack.Push(s);
while (stack.Count != 0)
{
s = stack.Pop();
foreach (Int64 i in adj[s])
{
if (!visited[i])
{
visited[i] = true;
stack.Push(i);
streetCounter++;
}
}
if (stack.Count == 0)
{
for (Int64 ii = 0; ii < v; ii++)
{
if (visited[ii] != true)
{
stack.Push(ii);
LibraryCounter++;
streetCounter--;
break;
}
}
}
}
result.Add(LibraryCounter);
result.Add(streetCounter);
return result;
}
class Program
{
static void Main(string[] args)
{
List<Int64>[] adj;
Int64 q = Convert.ToInt32(Console.ReadLine()); //Number of queries
Int64 costLib =0;
Int64 costStr =0;
List<Int64> result;
for (Int64 a0 = 0; a0 < q; a0++)
{
string[] tokens_n = Console.ReadLine().Split(' ');
Int64 n = Convert.ToInt32(tokens_n[0]); //Number of cities
Int64 m = Convert.ToInt32(tokens_n[1]); //Number of streets
Int64 x = Convert.ToInt64(tokens_n[2]); //Cost of library
Int64 y = Convert.ToInt64(tokens_n[3]); //Cost of street
adj = Graph(n);
costLib = x;
costStr = y;
for (Int64 a1 = 0; a1 < m; a1++)
{
string[] tokens_city_1 = Console.ReadLine().Split(' ');
Int64 city_1 = Convert.ToInt32(tokens_city_1[0]);
Int64 city_2 = Convert.ToInt32(tokens_city_1[1]);
AddEdge(city_1-1, city_2-1,adj);
}
if (x <= y)
{
Console.WriteLine(costLib * n);
}
else
{
result = DFS(n,adj);
Console.WriteLine(result[1] * costStr + result[0] * costLib);
}
}
}
static List<Int64>[] Graph(Int64 v)
{
Int64 Vertices = v;
List<Int64>[] adj = new List<Int64>[v];
for (Int64 i = 0; i < v; i++)
{
adj[i] = new List<Int64>();
}
return adj;
}
static void AddEdge(Int64 v, Int64 w, List<Int64>[] adj)
{
adj[v].Add(w);
}
static List<Int64> DFS(Int64 v, List<Int64>[] adj)
{
Int64 s = 0;
Int64 streetCounter = 0;
Int64 LibraryCounter = 1;
bool[] visited = new bool[v];
List<Int64> result = new List<Int64>();
Stack<Int64> stack = new Stack<Int64>();
visited[s] = true;
stack.Push(s);
while (stack.Count != 0)
{
s = stack.Pop();
foreach (Int64 i in adj[s])
{
if (!visited[i])
{
visited[i] = true;
stack.Push(i);
streetCounter++;
}
}
if (stack.Count == 0)
{
for (Int64 ii = 0; ii < v; ii++)
{
if (visited[ii] != true)
{
stack.Push(ii);
LibraryCounter++;
streetCounter--;
break;
}
}
}
}
result.Add(LibraryCounter);
result.Add(streetCounter);
return result;
}