Оптимизация программы по времени работы алгоритма ⇐ JAVA

[Anonymous]

Я реализую пересечение матроидов, матроид графа (независимый набор = ациклический набор ребер) и цветовой матроид (независимый набор = все ребра набора имеют разные цвета). Я использую следующий алгоритм для поиска максимального пересечения матроидов:
J = ∅
isMaximal = false
while not isMaximal:
construct the exchange graph D_{M1, M2}(J)
X1 ← {z ∈ S \ J | J + z ∈ I1}
X2 ← {z ∈ S \ J | J + z ∈ I2}
P ← shortest alternating path from X1 to X2
if P ≠ ∅:
J ← J Δ V(P)
else:
isMaximal = true

но у меня ограничение по времени. Как я могу оптимизировать свою программу? Спасибо за ответ.
(Для поиска кратчайшего пути в графе обмена я использую BFS, для проверки ацикличности набора ребер я использую DSU).
Код:
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.*;

public class matroids_F {
static class Edge {
int u, v, color, index;

public Edge(int u, int v, int color, int index) {
this.u = u;
this.v = v;
this.color = color;
this.index = index;
}
}

public static List findRainbow(int n, List edges) {
Set B = new HashSet();
boolean[] used = new boolean[100];

while (true) {
Set X = new HashSet();
for (Edge edge : edges) {
if (!B.contains(edge) && graphCheck(B, edge, n)) {
X.add(edge);
System.err.println("X - " + edge.u + ", " + edge.v + ", " + edge.color + ", " + edge.index);
}
}

System.err.println("====");

Set Y = new HashSet();
for (Edge edge : edges) {
if (!B.contains(edge) && colorCheck(edge, used)) {
Y.add(edge);
System.err.println("Y - " + edge.u + ", " + edge.v + ", " + edge.color + ", " + edge.index);
}
}

System.err.println("====");

if (!Collections.disjoint(X, Y)) {
for (Edge edge : X) {
System.err.println("checking edge = " + edge.u + " " + edge.v + " " + edge.color + " " + edge.index);
if (Y.contains(edge)) {
System.err.println("adding edge " + edge.u + " " + edge.v + " " + edge.color + " " + edge.index);
B.add(edge);
used[edge.color] = true;
break;
}
}
continue;
}

List p = findPath(X, Y, edges, B, n, used);

if (p == null) {
break;
}
for (Edge edge : p) {
if (B.contains(edge)) {
B.remove(edge);
used[edge.color] = false;
} else {
B.add(edge);
used[edge.color] = true;
}
}
}

return new ArrayList(B);
}

private static boolean graphCheck(Set B, Edge edge, int n) {
UnionFind uf = new UnionFind(n);
for (Edge e : B) {
uf.union(e.u, e.v);
}
return uf.find(edge.u) != uf.find(edge.v);
}

private static boolean colorCheck(Edge edge, boolean[] used) {
return !used[edge.color];
}

private static List findPath(Set X, Set Y, List edges, Set B, int n, boolean[] used) {
Map edgeInd = new HashMap();
Map indEdge = new HashMap();
List adjList = new ArrayList();
int m = edges.size();

for (int i = 0; i < m; i++) {
adjList.add(new ArrayList());
edgeInd.put(edges.get(i), i);
indEdge.put(i, edges.get(i));
}

for (Edge y : edges) {
int i = edgeInd.get(y);
if (B.contains(y)) {
for (Edge x : edges) {
Set B_new = new HashSet(B);
B_new.remove(y);
if (!B.contains(x) && graphCheck(B_new, x, n)) {
int j = edgeInd.get(x);
adjList.get(i).add(j);
}
}
} else {
for (Edge x : B) {
Set B_new = new HashSet(B);
B_new.remove(y);
if (!used[x.color]) {
int j = edgeInd.get(x);
adjList.get(i).add(j);
}
}
}
}

adjList.add(new ArrayList());
for (Edge edge : X) {
adjList.get(m).add(edgeInd.get(edge));
}

Queue q = new LinkedList();
int[] p = new int[m + 1];
Arrays.fill(p, -1);
q.add(m);

while (!q.isEmpty()) {
int c = q.poll();
for (int w : adjList.get(c)) {
if (p[w] == -1) {
p[w] = c;
q.add(w);

if (Y.contains(indEdge.get(w))) {
List path = new ArrayList();
for (int v = w; v != m; v = p[v]) {
path.add(indEdge.get(v));
}
return path;
}
}
}
}
return null;
}

static class UnionFind {
int[] p, r;

UnionFind(int n) {
p = new int[n];
r = new int[n];
for (int i = 0; i < n; i++) {
p = i;
}
}

int find(int u) {
if (p != u) {
p = find(p);
}
return p;
}

void union(int u, int v) {
int x = find(u);
int y = find(v);
if (x == y) {
return;
}
if (r[x] > r[y]) {
p[y] = x;
} else if (r[x] < r[y]) {
p[x] = y;
} else {
p[y] = x;
r[x]++;
}
}
}

public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new File("rainbow.in"));
PrintWriter out = new PrintWriter("rainbow.out");

int n = in.nextInt();
int m = in.nextInt();
List edges = new ArrayList();

for (int i = 0; i < m; i++) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
int color = in.nextInt() - 1;
edges.add(new Edge(u, v, color, i + 1));
}

in.close();

List forest = findRainbow(n, edges);
out.println(forest.size());
for (Edge edge : forest) {
out.print(edge.index + " ");
}

out.close();
}
}


Подробнее здесь: https://stackoverflow.com/questions/793 ... -algorithm