a. You have 5 problems in this assignment.
b. G++ compiler will be used to compile your source codes.
c. Your program will be tested on Ubuntu 16.04.
d. You are not allowed to use global variables in your
implementation.
e. Your program will get two arguments, input and output file
names, from the command line:
>> Your_Executable INPUT_FILE_NAME
OUTPUT_FILE_NAME
1.
Given a number ? , we initially have ?+1 different sets which are {0}, {1}, {2}, ... , {?}.
Your program should support two operations on those sets: 1)
union two sets, and 2) check whether two elements are contained by
the same set.
Input:
In the first line, two integers ? (1 <= ? <= 1,000,000) and ?
(1 <= ? <= 100,000) are given where ? is the number of
operations that will be sequentially performed.
The following ? lines specify the operations.
A line having a format of “0 ? ?” indicates a union operation of set ? and set ? containing elements ? and ?, respectively (? ∈ ?, ? ∈ ?).
Similarly, a line beginning with ‘1’ ask you to check whether ?
and ? are in the same set.
Output:
For each checking operation, you are required to answer ‘Y’ if two
elements are in the same set.
Otherwise, print ‘N’.
Sample input
6 5
1 0 3
0 1 2
0 3 4
0 1 4
1 2 3
Sample Output
N
Y
2.
Given a weighted undirected graph, provide the cost of a minimum
spanning tree.
Input:
In the first line, two integers ? (1 <= ? <= 10,000) and ? (1
<= ? <= 200,000) are given where ? and ? are the number of
vertices and edges of the graph, respectively.
The following lines describes ? edges in a format of “? ? ?” indicating that the graph has an edge between vertices ? and ? with cost of ? .
Note that the vertex index begins with 1 and the cost ? can be
negative but |?| < 1,000,000.
Output:
You are required to output the cost of a minimum spanning tree.
Sample input
3 3
1 2 1
1 3 2
2 3 3
Sample Output
3
3.
Given a weighted undirected graph, provide the cost of the second minimum spanning tree.
The second minimum spanning tree has the minimum cost except MSTs.
In the figure, the left and right subfigures show the MST and the second MST, respectively.
Input:
In the first line, two integers ? (1 <= ? <= 50,000) and ? (1
<= ? <= 200,000) are given where ? and ? are the number of
vertices and edges of the graph, respectively.
The following lines describes ? edges in a format of “? ? ?” indicating that the graph has an edge between vertices ? and ? with cost of ?.
Note that the vertex index begins with 1 and edge weights are positive.
Output:
You are required to output the cost of the second minimum spanning
tree. You can output "-1” if such tree does not exist.
Sample Input
7 12
1 2 8
1 3 5
2 3 10
44 2 4 2
2 5 18
3 4 3
3 6 16
4 5 12
4 6 30
4 7 14
5 7 4
6 7 26
Sample Output
44
4.
We have a network which is defined by the dependency and data transfer time among computers.
For instance, if a computer ? depends on a computer ? with the transfer time ?, then any data can be transferred from ? to ? in ? seconds.
Unfortunately, a computer in our network is infected with a
virus. The virus will be propagated to the other computers which
depend on the infected computers.
When a computer ? is just infected, the computer ? will be infected
after ? seconds, if ? depends on ? with time ?.
We want to determine the number of computers that will be infected and the last time of infection from the first infection.
Input:
In the first line, three integers ? (1 <= ? <= 10,000), ? (1
<= ? <= 100,000), and ? are given where ?, ?, and ? are the
number of computers, the number of dependencies, and the index of
first infected computer, respectively.
The following lines describe ? dependencies in a format of “? ? ?” indicating that the computer ? depends on ? with transfer time of ?, where “?≠?" and 0 <= ? <= 1000.
Note that the vertex index begins with 1 and you can assume that the dependency is unique.
Output:
You are required to output the number of infected computers and
time of the last infection from the first infection
Sample input
3 3 1
2 1 2
3 1 8
3 2 4
Sample Output
3 6
5.
We would like to cross over a river by stepstones. The position
of a stepstone is represented by (?, ?).
You can jump to another stepstone, however, you have certain
constraint due to your physical ability.
When you are at (?, ?), you are only allowed to jump to stones at
(?′, ?′) where |? - ?′| <= 2 and |? - ?′| <= 2 .
For instance, you can jump from (0,0) to (2,2) or (2,1) , but you cannot move to (3,0).
The goal is reaching a line which is parallel to ?-axis. You are required to find a shortest path from (0,0) to the goal line in terms of the sum of distances.
The distance between two stones at (?, ?) and (?′, ?′) is the Euclidean distance
Input:
In the first line, two integers ? (1 <= ? <= 50,000), and ?
are given where ? and ? are the number of stepstones and the ?
coordinate of the goal line, respectively.
The following lines describe the position of ? stepstones in a
format of “? ?” where ? and ? are integers.
Note that 0 <= ?, ?, ? <= 1,000,000
Output:
Provide the distance of shortest path by rounding off to the
nearest integer.
(The exact distance in the following sample is 8.47 ⋯ . You need to
answer 8 by rounding off the exact distance.)
Sample input
5 3
1 2
6 3
4 1
3 2
0 2
Sample Output
8
(1).
#include<stdio.h>
int find(int parent[],int i){
while(parent[i]>0)
i=parent[i];
return i;
}
void uni(int parent[],int p,int q){
int k = find(parent,p);
if(k == p)
parent[p] = q;
else
parent[k] = q;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
int parent[n];
for(int i=0;i<n;i++)
parent[i] = -1;
for(int i=0;i<m;i++){
int c,d,e;
scanf("%d%d%d",&c,&d,&e);
switch(c){
case 0:
uni(parent,d,e);
break;
case 1:
if(find(parent,d) == find(parent,e))
printf("Y\n");
else
printf("N\n");
break;
}
}
return 0;
}
output:
6 5
1 0 3
0 1 2
0 3 4
0 1 4
1 2 3
N
Y
a. You have 5 problems in this assignment. b. G++ compiler will be used to compile...
C++ programing question22 Minimum spanning tree Time limit: 1 second Problem Description For a connected undirected graph G = (V, E), edge e corresponds to a weight w, a minimum weight spaning tree can be found on the graph. Into trees. Input file format At the beginning, there will be a positive integer T, which means that there will be T input data. The first line of each input has two positive integers n,m, representing n points and m edges...
Please help me with this C++ I would like to create that uses a minimum spanning tree algorithm in C++. I would like the program to graph the edges with weights that are entered and will display the results. The contribution of each line will speak to an undirected edge of an associated weighted chart. The edge will comprise of two unequal non-negative whole numbers in the range 0 to 99 speaking to diagram vertices that the edge interfaces. Each...
Problem definition: Give the program that implement Prim’s algorithm. Input: First line is N, denotes the amount of test case, then there are Ns graph data with an option number (determine whether output the selected edges or not). Each graph is undirected and connected, it is composed of V (the number of vertices, <= 1000), E (the number of edges, <=10000), then followed by Es edges which are denoted by pair of vertex and weight (e.g., 2 4 10 means...
IN JAVA Given is a weighted undirected graph G = (V, E) with positive weights and a subset of its edges F E. ⊆ E. An F-containing spanning tree of G is a spanning tree that contains all edges from F (there might be other edges as well). Give an algorithm that finds the cost of the minimum-cost F-containing spanning tree of G and runs in time O(m log n) or O(n2). Input: The first line of the text file...
Preferably in python but java is good too Task 1: Minimum Spanning Trees For this warm-up task you are to implement any efficient minimum spanning tree algorithm that takes a sequence of edge-weighted graphs and outputs the minimum cost weight of a spanning tree of each Input Format For this assignment we use adjacency matrices with positive integer weights. Here a zero entry at row i and column J indicates that no edge i] exists in the graph. The first...
in c++ The Bellman-Ford Algorithm In this assignment, you are asked to implement the Bellman-Ford Algorithm which solves the single-source shortest-paths problem. Specifically, you are given as input a directed graph G = (V. E) with weight w(u, v) on each edge (u, v) E E along with a source vertex s EV. Edges may have negative weights. Input The input has the following format. There are two integers on the first line. The first integer represents the number of...
Let G be an undirected graph and let X be a subset of the vertices of G. A connecting tree on X is a tree composed out of the edges of G that contains all the vertices in X. One way to compute a connecting tree consists of two steps: (1) Compute a minimum spanning tree T over G. (2) Delete all the edges out of T not needed to connect vertices in X. Give an algorithm(Pseudo-code) to carry out...
COMP Discrete Structures: Please answer completely and clearly. (3). (5). x) (4 points) If k is a positive integer, a k-coloring of a graph G is an assignment of one of k possible colors to each of the vertices/edges of G so that adjacent vertices/edges have different colors. Draw pictures of each of the following (a) A 4-coloring of the edges of the Petersen graph. (b) A 3-coloring of the vertices of the Petersen graph. (e) A 2-coloring (d) A...
Please submit only Python source code. 1. Arithmetic trees 50 marks You are given an input file with multiple pairs of input lines. The first line of each pair is a tree given as a predecessor array. The second line is the value at the corresponding node. Values at leaf nodes (nodes with no children) are integers. At non-leaf nodes, the two possible values are + or *. The tree represents an arithmetic expression where the value at a non-leaf...
Question 4t Write the correct integer values in the boxes. For this question, working is not required and will not be marked. This question is about the number of spanning trees of a graph. In a lecture we used complementary counting to calculate that the graph depicted at left has exactly eight spanning trees. By adding just one more edge to this graph we arrive at the complete graph K depicted at right. A spanning tree has -1 3 edges...