4
\$\begingroup\$

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:

enter image description here

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);
            connsFrom[a].add(e);
            connsTo[b].add(e);
        }

        // 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) {
                    translators.add(e2.to);
                    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<>();
        q.add(new Edge(source, 0));

        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);
                    ne.path.add(e2);
                    q.add(ne);
                }                
            }

        }

        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?

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Devon Parsons Feb 19 '15 at 4:17
  • \$\begingroup\$ @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. \$\endgroup\$ – Olavi Mustanoja Feb 19 '15 at 4:20
  • \$\begingroup\$ Ah, I understand, I thought you were displaying the available translators, but you are displaying the translations required \$\endgroup\$ – Devon Parsons Feb 19 '15 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.