Bidirectional spanning tree

Question

I came across this question from interviewstreet.com

Machines have once again attacked the kingdom of Xions. The kingdom of Xions has N cities and N-1 bidirectional roads. The road network is such that there is a unique path between any pair of cities.

Morpheus has the news that K Machines are planning to destroy the whole kingdom. These Machines are initially living in K different cities of the kingdom and anytime from now they can plan and launch an attack. So he has asked Neo to destroy some of the roads to disrupt the connection among Machines i.e after destroying those roads there should not be any path between any two Machines.

Since the attack can be at any time from now, Neo has to do this task as fast as possible. Each road in the kingdom takes certain time to get 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 he will require to disrupt the connection among machines.

Sample Input First line of the input contains two, space-separated integers, N and K. Cities are numbered 0 to N-1. Then follow N-1 lines, each containing three, space-separated integers, x y z, which means there is a bidirectional road connecting city x and city y, and to destroy this road it takes z units of time. Then follow K lines each containing an integer. Ith integer is the id of city in which ith Machine is currently located.

Output Format Print in a single line the minimum time required to disrupt the connection among Machines.

Sample Input

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

Sample Output

10

Explanation Neo can destroy the road connecting city 2 and city 4 of weight 5 , and the road connecting city 0 and city 1 of weight 5. As only one road can be destroyed at a time, the total minimum time taken is 10 units of time. After destroying these roads none of the Machines can reach other Machine via any path.

Constraints

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

Can someone give idea how to approach the solution.

Answer 1

All the three answers will lead to correct solution but you can not achieve the solution within the time limit provided by interviewstreet.com. You have to think of some simple approach to solve this problem successfully.

HINT: start from the node where machine is present.

Answer 2

The kingdom has N cities, N-1 edges and it's fully connected, therefore our kingdom is tree (in graph theory). At this picture you can see tree representation of your input graph in which Machines are represented by red vertices.

By the way you should consider all paths from the root vertex to all leaf nodes. So in every path you would have several red nodes and during removing edges you should take in account only neighboring red nodes. For example in path 0-10 there are two meaningfull pairs - (0,3) and (3,10). And you must remove exactly one node (not less, not more) from each path which connected vertices in pairs.

I hope this advice was helpful.

Answer 3

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

This kind of problem asks for a greedy solution; I'd go for a modification of Kruskal's algorithm:

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

Take 1 edge (road) at a time, order by descending weight (starting with roads most costly to destroy). For this edge (which necessarily connects two components - the graph is a tree):

• if both neigboring components contain a machine-occupied city, this road must be destroyed, mark it as such
• otherwise, merge the neigboring components into one. If one of them contained a machine-occupied city, so does the merged component.

When you're done with all edges, return the sum of costs for the destroyed roads.

Complexity will be the same as Kruskal's algorithm, that is, almost linear for well chosen data structure and sorting method.

Answer 4

pjotr has a correct answer (though not quite asymptotically optimal), but this statement

This kind of problem asks for a greedy solution

really requires proof, as in the real world (as distinguished from competitive programming), there are several problems of this “kind” for which the greedy solution is not optimal (e.g., this very same problem in general graphs, which is called multiterminal cut and is NP-hard). In this case, proof consists of verifying the matroid axioms. Let a set of edges A ⊆ E be independent if the graph (V, E ∖ A) has exactly |A| + 1 connected components containing at least one machine.

Independence of the empty set. Trivial.

Hereditary property. Let A be an independent set. Every edge e ∈ A joins two connected components of the graph (V, E ∖ A), and every connected component contains at least one machine. In putting e back in the graph, the number of connected components containing at least one machine decreases by 1, so A ∖ {e} is also independent.

Augmentation property. Let A and B be independent sets with |A| < |B|. Since (V, E ∖ B) has more connected components than (V, E ∖ A), there exists by the pigeonhole principle a pair of machines u, v such that u and v are disconnected by B but not by 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. The removal of A ∪ {e} induces one more connected component containing at least one machine than A, so A ∪ {e} is independent, as required.

Answer 5

Start performing a DFS from either of the machine nodes. Also, keep track of the edge with min weight encountered so far. As soon as you find the next node which also contains a machine, delete the min edge recorded so far. Start DFS from this new node now. Repeat until you have found all nodes where the machines exists.

Should be of the O(N) that way !!

Answer 6

I write some code, and pasted 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);
}
}