Bidirectional spanning tree

Question

I came across this question with interviewstreet.com

The machines again attacked the kingdom of Zion. The kingdom of Xions has N cities and N-1 bidirectional roads. The road network so that there is a unique path between any pair of cities.

There is news in Morpheus that K Machines plan to destroy the entire kingdom. These machines originally live in K different cities of the kingdom, and at any time they can plan and launch an attack. Therefore, he asked Neo to destroy some of the roads in order to break the connection between the cars, after the destruction of these roads there should be no way between any two cars.

Since the attack can be at any time from now on, Neo must complete this task as quickly as possible. Each road in the kingdom takes a certain time to be destroyed, and they can be destroyed only one at a time.

You need to write a program that tells Neo the minimum amount of time it will require to break the connection between the machines.

Input Example The first line of input contains two integers, N and K, separated by spaces. Cities are numbered from 0 to N-1. Then follow the N-1 lines, each of which contains three integers separated by spaces, xyz, which means that there is a two-way road connecting city x and city y, and z units of time are required to destroy this road. Then K lines follow, each of which contains an integer. Ith integer is the identifier of the city where I am currently located in the car.

Output format Printing in one line the minimum time required to break the connection between machines.

Input example

5 3 2 1 8 1 0 5 2 4 5 1 3 4 2 4 0 

Output result

 10 

Explanation Neo can destroy a road connecting city 2 and city 4 of weight 5, and a road connecting city 0 and city 1 of weight 5. As only one road can be destroyed at a time, the total minimum time is 10 time units. After the destruction of these roads, not one of the vehicles can reach another vehicle in any way.

Limitations

 2 <= N <= 100,000 2 <= K <= N 1 <= time to destroy a road <= 1000,000 

Can someone give an idea of ​​how to approach the solution.

Answer 1

All three answers will lead to the right decision, but you will not be able to reach a decision within the time period provided by the interviewer. You should come up with some simple approach to successfully solve this problem.

TIP: start with the node where the machine is located.

Answer 2

There are N cities in the kingdom, the edges are N-1 and are completely connected, therefore our kingdom is tree (in graph theory). In this image you can see a tree view of your input graph, in which cars are represented by red peaks.

By the way, you should consider all the paths from the root vertex to all leaf nodes. Thus, on each path you will have several red nodes, and when deleting the edges you should only consider neighboring red nodes. For example, on path 0-10 there are two significant pairs - (0.3) and (3.10). And you must remove exactly one node (no less, no more) from each path that connected the vertices in pairs.

I hope this tip was helpful.

Answer 3

As others say, a connected graph with N vertices and edges N-1 is a tree.

This type of problem requires a greedy solution; I would choose a modification of the Kruskal algorithm :

Start with a set of N components - 1 for each node (city). Keep track of which components contain the city occupied by the machine.

Take 1 edge (road) at a time, order in descending order of weight (starting from the roads that are most expensive to destroy). For this edge (which necessarily connects two components - the graph is a tree):

• If both neighboring components contain a city occupied by a machine, this road must be destroyed, mark it as such
• otherwise merge related components into one. If one of them contains a city occupied by a machine, then the combined component.

When you are done with all the edges, return the sum of the costs of the destroyed roads.

The complexity will be the same as the Kruskal algorithm, i.e. almost linear for a well-chosen data structure and sorting method.

Answer 4

pjotr has the correct answer (although not quite asymptotically optimal), but this statement

This problem sets a greedy solution.

really requires proof, since in the real world (unlike competitive programming) there are several problems of this “kind” for which the greedy solution is not optimal (for example, this is a problem in general graphs called a multi-terminal cut and NP-hard). In this case, the proof consists in checking the matroid axioms. Let the set of edges A & subseteq; E are independent if the graph (V, E & setminus; A) has exactly | A | + 1 component containing at least one machine.

Independence of an empty set. Trivial.

Inherited property. Let A be an independent set. Each edge is e & in; A connects two connected components of the graph (V, E & setminus; A), and each connected component contains at least one machine. When e returns to the graph, the number of connected components containing at least one machine decreases by 1, therefore A & setminus; {e} is also independent.

Extension property. Let A and B be independent sets with | A | <| B |. Since (V, E & setminus; B) has more connected components than (V, E & setminus; A), by the principle of pigeon, there are a pair of machines u, v such that u and v are disconnected with B, but not through A Since there is exactly one path from u to v, B contains at least one edge e on this path, and A cannot contain e. Removing A & cup; {e} induces another connected component containing at least one machine than A, therefore A & cup; {e} is independent if required.

Answer 5

Start DFS from any host on the machine. In addition, keep track of the edges with the least weight found so far. Once you find the next node, which also contains the machine, delete the minimum edge written so far. Launch DFS from this new node. Repeat until you find all the nodes where the machines exist.

Must be O (N) that way !!

Answer 6

I write code and insert all the tests.

 #include <iostream> #include<algorithm> using namespace std; class Line { public: Line(){ begin=0;end=0; weight=0; } int begin;int end;int weight; bool operator<(const Line& _l)const { return weight>_l.weight; } }; class Point{ public: Point(){ pre=0;machine=false; } int pre; bool machine; }; void DP_Matrix(); void outputLines(Line* lines,Point* points,int N); int main() { DP_Matrix(); system("pause"); return 0; } int FMSFind(Point* trees,int x){ int r=x; while(trees[r].pre!=r) r=trees[r].pre; int i=x;int j; while(i!=r) { j=trees[i].pre; trees[i].pre=r; i=j; } return r; } void DP_Matrix(){ int N,K,machine_index;scanf("%d%d",&N,&K); Line* lines=new Line[100000]; Point* points=new Point[100000]; N--; for(int i=0;i<N;i++) { scanf("%d%d%d",&lines[i].begin,&lines[i].end,&lines[i].weight); points[i].pre=i; } points[N].pre=N; for(int i=0;i<K;i++) { scanf("%d",&machine_index); points[machine_index].machine=true; } long long finalRes=0; for(int i=0;i<N;i++) { int bP=FMSFind(points,lines[i].begin); int eP=FMSFind(points,lines[i].end); if(points[bP].machine&&points[eP].machine){ finalRes+=lines[i].weight; } else{ points[bP].pre=eP; points[eP].machine=points[bP].machine||points[eP].machine; points[bP].machine=points[eP].machine; } } cout<<finalRes<<endl; delete[] lines; delete[] points; } void outputLines(Line* lines,Point* points,int N){ printf("\nLines:\n"); for(int i=0;i<N;i++){ printf("%d\t%d\t%d\n",lines[i].begin,lines[i].end,lines[i].weight); } printf("\nPoints:\n"); for(int i=0;i<=N;i++){ printf("%d\t%d\t%d\n",i,points[i].machine,points[i].pre); } }