# Minimum amount of edges that needs to be traversed to visit all vertices… or something like that

So I have this problem, where I'm given m connections over n vertices. The vertices are labeled 1...n.

Example input:

4 5
1 2
2 3
2 4
3 1
3 4


The first row contains the numbers n and m. The following m rows tells me what connections exist. It's safe to assume the connections contain every number 1...n at least once.

The above input would represent a graph like below:

# Problem Description

The actual problem states, that there are m translations that need to be done. What is the minimum amount of translators that have to be hired, so that all the translations can be done? The translators can work together, for example, if translator A can translate from language 1 to language 2, and translator B can translate from language 3 to language 1, then a translation 3->2 can be done with those two translators working together (3->1->2).

Here is my working code:

import java.util.*;

public class Translators {

public static int n;
public static ArrayList<Edge>[] connsFrom;
public static ArrayList<Edge>[] connsTo;

public static void main(String[] args) {

// an external class working like Scanner, but faster
IO io = new IO();

n = io.nextInt();     // number of languages
int m = io.nextInt(); // number of translations

// number of translations that need be done to language i
int[] to = new int[n+1];

// number of translations that need be done from language i
int[] from = new int[n+1];

// translations that need be done from language i
connsFrom = new ArrayList[n+1];

// translations that need be done to language i
connsTo = new ArrayList[n+1];

// init
for (int i = 1; i <= n; i++) {
connsFrom[i] = new ArrayList<>();
connsTo[i] = new ArrayList<>();
}

for (int i = 0; i < m; i++) {
int a = io.nextInt();    // translation from
int b = io.nextInt();    // translation to
Edge e = new Edge(b, 0);
}

// init an edge's weight to 1 when it's the only edge from a vertex,
// or only edge to a vertex.
for (int i = 1; i <= n; i++) {
if (connsFrom[i].size() == 1) connsFrom[i].get(0).weight = 1;
if (connsTo[i].size() == 1) connsTo[i].get(0).weight = 1;
}

// hired translators
HashSet<Integer> translators = new HashSet<>();

for (int i = 1; i <= n; i++) {
for (Edge e : connsFrom[i]) {

// find the path that has the biggest cost
ArrayList<Edge> path = findPath(i, e.to);

// hire all translators on the path, and change the
// weight of all used edges to 1.
for (Edge e2 : path) {
e2.weight = 1;
}
}
}

System.out.println(translators.size());

}

/**
* Dijkstra, returning the path with maximal cost.
*/
public static ArrayList<Edge> findPath(int source, int goal) {
int[] approx = new int[n+1];
boolean[] fin = new boolean[n+1];

PriorityQueue<Edge> q = new PriorityQueue<>();

while (!q.isEmpty()) {
Edge e = q.poll();

if (fin[e.to]) continue; // already visited
fin[e.to] = true;

if (e.to == goal) return e.path;

for (Edge e2 : connsFrom[e.to]) {
if (e.weight + e2.weight > approx[e2.to]) {
approx[e2.to] = e.weight + e2.weight;

Edge ne = new Edge(e2.to, e.weight + e2.weight);
ne.path = new ArrayList<>(e.path);
}
}

}

return new ArrayList<>();
}

}

class Pair {
public int a;
public int b;
public Pair(int a, int b) {
this.a = a;
this.b = b;
}

@Override
public boolean equals(Object o) {
Pair p = (Pair) o;
return a == p.a && b == p.b;
}

@Override
public int hashCode() {
int hash = 7;
hash = 61 * hash + this.a;
hash = 61 * hash + this.b;
return hash;
}
}

class Edge implements Comparable<Edge> {
public int to;
public int weight;
public ArrayList<Edge> path = new ArrayList<>();
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}

@Override
public int compareTo(Edge o) {
return Long.compare(o.weight, weight); // bigger first
}

@Override
public String toString() {
return "-" + weight + "-> " + to;
}
}


My idea was to init the weight of all the edges to 0 at first, but if an edge is the only edge going to or coming from a vertex, change its weight to 1. Also, when we find a path from a to b, we change the weight of all the edges on that path to 1. This way the searching algorithm always finds a path that has the most vertices that have been used before.

This code gives me the correct answer, however, n can be as big as 5 * 10^4, and m can be as big as 10^5, for which the code runs too slow.

My question: is there a way of optimizing this? Do I need a different approach altogether, or can my code be tweaked?

• Is it your intention that in the example you cannot translate from language 4 to any other language? Does that matter? It's a bit strange that in this particular scenario a translator can only translate one way. – Devon Parsons Feb 19 '15 at 4:17
• @DevonParsons If there is an edge from vertex v to u, it simply means that a translation from v to u must be done. Language 4 doesn't have edges to other languages because there mustn't be a translation from language 4 to any other language. – Olavi Mustanoja Feb 19 '15 at 4:20
• Ah, I understand, I thought you were displaying the available translators, but you are displaying the translations required – Devon Parsons Feb 19 '15 at 6:01