Road#6576
Run Kruskal's algorithm on the initial graph. In the set , store the edges that belong to the minimum spanning tree. Next, check whether the given edge is part of this spanning tree. To do this, we need to verify whether the pair or is contained in the set .
Example
The graphs given in the examples have the following form:
Algorithm implementation
Define a structure for a graph edge that contains a pair of vertices and the edge weight. Define an array of edges .
struct Edge
{
int u, v, dist;
};
vector<Edge> e;Define an array , which is used to implement the disjoint set union structure.
vector<int> parent;The function Repr finds the representative of the set to which vertex belongs.
int Repr(int n)
{
while(n != parent[n]) n = parent[n];
return n;
}The function Union merges the sets containing the elements and .
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 serves as a comparator for sorting the edges.
int lt(Edge a, Edge b)
{
return (a.dist < b.dist);
}The main part of the program. Process several test cases.
scanf("%d", &tests);
while (tests--)
{Read the input data. Initialize the array.
scanf("%d %d %d %d", &n, &m, &p, &q);
parent.resize(n + 1);
for (i = 1; i <= n; i++) parent[i] = i;Read the graph edges.
e.resize(m);
for (i = 0; i < m; i++)
scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].dist);Sort the graph edges in ascending order of their weights.
sort(e.begin(), e.end(), lt);For each test case, reset the variable . It takes the value or depending on whether the edge belongs to the minimum spanning tree.
flag = 0;Run Kruskal's algorithm to construct the minimum spanning tree. If the edge (e[i].u, e[i].v) is included in the spanning tree, check whether it matches the edge .
for (i = 0; i < m; i++)
if (Union(e[i].u, e[i].v))It is necessary to check two conditions: (e[i].u, e[i].v) = (p, q) и (e[i].u, e[i].v) = (q, p).
if ((e[i].u == p && e[i].v == q) ||
(e[i].u == q && e[i].v == p))
{If the edge (e[i].u, e[i].v) matches or , set flag = 1 and break the loop.
flag = 1;
break;
}Depending on the value of the variable , print the answer.
if (flag)
puts("YES");
else
puts("NO");
}Algorithm implementation – set
Define a structure for a graph edge that contains a pair of vertices and the edge weight. Define an array of edges .
struct Edge
{
int u, v, dist;
};
vector<Edge> e;Define an array , which is used to implement the disjoint set union structure.
vector<int> parent;In the set , store the edges that belong to the minimum spanning tree.
set<pair<int, int> > s;The function Repr finds the representative of the set to which vertex belongs.
int Repr(int n)
{
while(n != parent[n]) n = parent[n];
return n;
}The function Union merges the sets containing the elements and .
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 serves as a comparator for sorting the edges.
int lt(Edge a, Edge b)
{
return (a.dist < b.dist);
}The main part of the program. Process several test cases.
scanf("%d", &tests);
while (tests--)
{Read the input data. Initialize the array.
scanf("%d %d %d %d", &n, &m, &p, &q);
parent.resize(n + 1);
for (i = 1; i <= n; i++) parent[i] = i;Read the graph edges.
e.resize(m);
for (i = 0; i < m; i++)
scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].dist);Sort the graph edges in ascending order of their weights.
sort(e.begin(), e.end(), lt);For each test case, clear the set .
s.clear();Run Kruskal's algorithm to construct the minimum spanning tree. If the edge (e[i].u, e[i].v) is included in the spanning tree, add it to the set .
for (i = 0; i < m; i++)
if (Union(e[i].u, e[i].v)) s.insert(make_pair(e[i].u, e[i].v));After the algorithm finishes, check whether the given edge belongs to the minimum spanning tree. To do this, we need to determine whether the pair or is contained in the set .
if ((s.find(make_pair(p, q)) != s.end()) ||
(s.find(make_pair(q, p)) != s.end()))
puts("YES");
else
puts("NO");
}Java implementation
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();
}
}