C++: Fast algorithm for finding minimum sum of cycle edges

Question

I have an undirected weighted graph and want to find the minimum sum of all cycles edges. That means if I have no cycle, the answer is 0. If I have one cycle the answer is the minimum edge weight of that cycle. And if I have more than one cycle it's the sum of those minimum weights.

My algorithm I implemented, uses some kind of Prims algorithm. I just add the heaviest edges and when a cycle would be formed the weight is summed to the answer value instead.

I thought it is correct as all my test cases show the right answer.

But somewhere has to be an error, I just couldn't find it yet.

struct connection {
    int a, b, cost;

    bool operator<(const connection rhs) const {
        return cost < rhs.cost || (cost == rhs.cost && (a < rhs.a || (a == rhs.a && b < rhs.b)));
    }
};

int n, m, researchers; // Amount of vertices, edges
std::list<connection> *adj; // Array of adjancency lists
std::list<int> *used;
std::set<connection> priorityQ;

void addEdge(int v, int w, int cost) {
    connection temp;
    temp.a = v;
    temp.b = w;
    temp.cost = cost;
    adj[v].push_back(temp);
    temp.a = w;
    temp.b = v;
    adj[w].push_back(temp);
}

bool isUsed(int u, int v) {
    for (std::list<int>::iterator it = used[u].begin(); it != used[u].end(); ++it) {
        int te = *it;
        if (te == v) return true;
    }
    return false;
}

void expand(int u) {
    for (std::list<connection>::iterator it = adj[u].begin(); it != adj[u].end(); ++it) {

        connection v = *it;

        if (isUsed(u, v.b)) continue;

        used[v.b].push_back(u);
        used[u].push_back(v.b);

        priorityQ.insert(v);
    }
}

void PrimR(int u, bool added[]) {
    added[u] = true;
    expand(u);
}

// Prim algorithm
void Prim(int u, bool added[]) {

    added[u] = true;

    expand(u);

    while (priorityQ.size() > 0) {
        connection now = *priorityQ.rbegin();
        priorityQ.erase(*priorityQ.rbegin());

        if (added[now.b]) {
            researchers += now.cost;
        }
        else {
            PrimR(now.b, added);

        }
    }

}

int main()
{

    int t;

    // loop over all test cases
    scanf("%d ", &t);
    for (int i = 1; i <= t; i++) {

        // read input nodes n, connections m
        scanf("%d %d", &n, &m);

        adj = new std::list<connection>[n];

        //read connections and save them
        for (int j = 0; j < m; j++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            addEdge(a - 1, b - 1, c);
        }

        researchers = 0;

        // Use of prim with heaviest edges first
        bool *added = new bool[n];
        used = new std::list<int>[n];

        for (int j = 0; j < n; j++) {
            added[j] = false;
        }

        for (int j = 0; j < n; j++) {
            if (!added[j]) {
                Prim(j, added);
            }
        }


        // print desired output
        printf("Case #%d: %d\n", i, researchers);

        delete[] adj;
        delete[] added;
        delete[] used;
    }
    return 0;
}

Do you know what I'm doing wrong?

Answer 1

I didn't consider, that between two nodes there could be multiple connections.

My following code solves this:

struct connection {
    int a, b, cost, id;

    bool operator<(const connection rhs) const {
        return cost < rhs.cost || (cost == rhs.cost && id < rhs.id);
    }
};

int n, m, researchers; // Amount of vertices, edges
std::list<connection> *adj; // Array of adjancency lists
std::set<connection> priorityQ;

void addEdge(int v, int w, int cost, int id) {
    connection temp;
    temp.a = v;
    temp.b = w;
    temp.cost = cost;
    temp.id = id;
    adj[v].push_back(temp);
    temp.a = w;
    temp.b = v;
    adj[w].push_back(temp);
}

void deleteEdge(int v, int w, int id) {
    for (std::list<connection>::iterator it = adj[v].begin(); it != adj[v].end(); ++it) {
        if ((*it).id == id) {
            adj[v].erase(it);
            break;
        }
    }
    for (std::list<connection>::iterator it = adj[w].begin(); it != adj[w].end(); ++it) {
        if ((*it).id == id) {
            adj[w].erase(it);
            break;
        }
    }
}

void expand(int u) {
    for (std::list<connection>::iterator it = adj[u].begin(); it != adj[u].end(); ++it) {

        connection v;
        v.a = (*it).a < (*it).b ? (*it).a : (*it).b;
        v.b = (*it).a < (*it).b ? (*it).b : (*it).a;
        v.cost = (*it).cost;
        v.id = (*it).id;

        priorityQ.insert(v);
    }
}

void PrimR(int u, bool added[]) {
    added[u] = true;
    expand(u);
}

// Prim algorithm
void Prim(int u, bool added[]) {

    added[u] = true;

    expand(u);

    while (priorityQ.size() > 0) {
        connection now = *priorityQ.rbegin();
        priorityQ.erase(*priorityQ.rbegin());

        deleteEdge(now.a, now.b, now.id);

        if (added[now.b] && added[now.a]) {
            researchers += now.cost;
        }
        else if (added[now.b]) {
            PrimR(now.a, added);
        }
        else if (added[now.a]) {
            PrimR(now.b, added);
        }
    }

}

int main()
{

    int t;

    // loop over all test cases
    scanf("%d ", &t);
    for (int i = 1; i <= t; i++) {

        // read input nodes n, connections m
        scanf("%d %d", &n, &m);

        adj = new std::list<connection>[n];

        //read connections and save them
        for (int j = 0; j < m; j++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);

            addEdge(a - 1, b - 1, c, j);
        }

        researchers = 0;

        // Use of prim with heaviest edges first
        bool *added = new bool[n];

        for (int j = 0; j < n; j++) {
            added[j] = false;
        }

        for (int j = 0; j < n; j++) {
            if (!added[j]) {
                Prim(j, added);
            }
        }


        // print desired output
        printf("Case #%d: %d\n", i, researchers);

        delete[] adj;
        delete[] added;
    }
    return 0;
}