6576. Road

In one country, there aren cities, numbered 1 to n. A civil engineer has to build public roads that connect all the cities together, i.e. it must be possible to travel from all cities to any other cities, maybe going through multiple cities. His team has surveyed several routes (candidate road between any two cities). Each route is a bidirectional connection between two cities. He can build a bidirectional road on the surveyed route for a specific cost (The shorter the route is the cheaper the road).

This engineer has never planned a road system in advance. He would just pick one of the routes based on his preference, and build a road until all the cities are connected.

Right now this engineer is going to build a road from the city p to the city q. With pressure from the government to reduce the cost, he asks you to write a program to decide, if he should build this road or not. Your program should say yes if the building of this road guaranteed that it can be part of the shortest road system that connects all cities together. Otherwise, your program should say no.

Input. The first line is a number of test cases t (t ≤ 10).

Each test case starts with a line contains 4 integers n, m, p and q. Here n (2 ≤ n ≤ 10000) is the number of cities in this road system, m (1 ≤ m ≤ 20000) is the number of surveyed routes, p and q (1 ≤ p ≤ n, 1 ≤ q ≤ n) indicate the route between two cities, that the engineer asks if he can build a road or not.

Then, the each of the following m lines contains 3 numbers u, v и w (1 ≤ u ≤ n, 1 ≤ v ≤ n, 1 ≤ w ≤ 400000) indicates that there are the bidirectional route of length w between u and v. The length of each road in the current system is unique. And, there is only one possible road between two cities. The input guarantees that at least one road system has a route between any two cities. All numbers are integer.

Output. For each test case, print YES if the engineer can build a road (p, q) as part of the shortest road system. Otherwise, print NO.

Sample input	Sample output
3 2 1 1 2 1 2 4 3 3 2 3 1 2 1 1 3 2 2 3 3 4 5 3 4 1 2 1 1 3 3 3 4 2 1 4 4 4 2 5	YES NO YES

SOLUTION

graphs – Kruskal algorithm

Algorithm analysis

Run the Kruskal’s algorithm on the input graph. In the set s include the edges of the graph that belong to the minimal spanning tree (MST). Next, check whether the given edge (p, q) belongs to the MST. To do this, check whether the pair (p, q) or (q, p) is in the set s.

Example

Graphs, given in the samples, have the form:

Algorithm realization

Declare  the structure of the graph edge (a pair of vertices and the weight of the edge).

struct Edge

{

int u, v, dist;

};

vector<Edge> e;

Declare an array parent used by the disjoint set system.

vector<int> parent;

In the set s we’ll store the edges that belong to MST.

set<pair<int, int> > s;

The function Repr finds a representative of the set that contains vertex n.

int Repr(int n)

{

while(n != parent[n]) n = parent[n];

return n;

}

Function Union unites sets that contain the elements x and y.

int Union(int x, int y)

{

x = Repr(x); y = Repr(y);

if (x == y) return 0;

parent[y] = x;

return 1;

}

The function lt is a comparator for sorting edges.

int lt(Edge a, Edge b)

{

return (a.dist < b.dist);

}

The main part of the program. Process multiple test cases.

scanf("%d", &tests);

while (tests--)

{

Read the input data. Initialize the arrays.

scanf("%d %d %d %d", &n, &m, &p, &q);

parent.resize(n + 1);

for (i = 1; i <= n; i++) parent[i] = i;

Read the edges of the graph.

e.resize(m);

for (i = 0; i < m; i++)

scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].dist);

Sort the edges in increasing order of their weights.

sort(e.begin(), e.end(), lt);

When processing the next test case, clear the set s.

s.clear();

Start the Kruskal algorithm that constructs MST. If the edge (e[i].u, e[i].v) will be included into MST, add it to the set s.

for (i = 0; i < m; i++)

if (Union(e[i].u, e[i].v)) s.insert(make_pair(e[i].u, e[i].v));

Check if the given edge (p, q) belongs to MST. To do this, check whether the pair (p, q) or (q, p) is in the set s.

if ((s.find(make_pair(p, q)) != s.end()) ||

(s.find(make_pair(q, p)) != s.end()))

puts("YES");

else

puts("NO");

}

Java realization

import java.util.*;

class Edge

{

int u, v, dist;

Edge (int u, int v, int dist)

{

this.u = u;

this.v = v;

this.dist = dist;

}

};

class Pair

{

int u, v;

Pair (int u, int v)

{

this.u = u;

this.v = v;

}

};

public class Main

{

static int mas[];

static int size[];

static int Repr(int n)

{

if (n == mas[n]) return n;

return mas[n] = Repr(mas[n]);

}

static int Union(int x,int y)

{

x = Repr(x); y = Repr(y);

if(x == y) return 0;

if (size[x] < size[y])

{

int temp = x; x = y; y = temp;

}

mas[y] = x;

size[x] += size[y];

return 1;

}

public static class MyFun implements Comparator<Edge>

{

public int compare(Edge a, Edge b)

{

return a.dist - b.dist;

}

}

public static class PairFun implements Comparator<Pair>

{

public int compare(Pair a, Pair b)

{

if (a.u == b.u) return a.v - b.v;

return a.u - b.u;

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

while(tests-- > 0)

{

int n = con.nextInt();

int m = con.nextInt();

int p = con.nextInt();

int q = con.nextInt();

mas = new int[n+1];

size = new int[n+1];

for(int i = 1; i <= n; i++)

{

mas[i] = i;

size[i] = 1;

}

Vector<Edge> v = new Vector<Edge>();

for(int i = 0; i < m; i++)

{

int x = con.nextInt();

int y = con.nextInt();

int dist = con.nextInt();

v.add(new Edge(x,y,dist));

}

Collections.sort(v, new MyFun());

TreeSet<Pair> s = new TreeSet<Pair>(new PairFun());

for(int i = 0; i < m; i++)

if (Union(v.get(i).u,v.get(i).v) == 1) s.add(new Pair(v.get(i).u,v.get(i).v));

if(s.contains(new Pair(p,q)) || s.contains(new Pair(q,p)))

System.out.println("YES");

else

System.out.println("NO");

}

con.close();

}

}