How do I correctly build my graph for the Hopcroft Karp Maximal Matching Algorithm in the current generic scenario given?

bholagabbar

I'm solving an algorithmic problem which required me to learn a Maximal Matching algorithm. After spending a day learning and implementing it from various sources, I have understood the algorithm.

However, I'm unable to apply the algorithm (build the graph) for the current scenario.

Here it goes: I have 'n' boys and 'm' girls. Each of them has a 'Dancing Skill' and a boy can be paired with another girl iff either of their skill difference differs by 1 point. That is, absolute value (boy skill-girl skill)<=1. I have to find the maximum number of pairs that can be formed.

I'm pretty sure my implementation of the Hopcroft Karp maximal matching algorithm is correct. The problem is the building of the graph. I have tried to build the graph in the following way in complexity O(n*m):

For each boy indexed 1 to n, Search for the indices of the girls whose skill difference differs by 1 point. If found, add an undirected edge to the graph. This seems entirely correct to me.

Could someone help me out?

Here is my code. As mentioned, the matching algorithm is right. The attention required is in the 'main' function where I build the graph:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
#define pb push_back
#define sz 100001

int boysSkillz[sz], girlsSkillz[sz];

//Maximal Matching begins
vector<int> adj[sz];
int pairU [sz], pairV[sz], dist[sz];

bool HK_Bfs(int m)
{
    queue<int> Q;
    for (int u=1; u<=m; u++)
    {
        if (pairU[u]==0)
        {
            dist[u] = 0;
            Q.push(u);
        }
        else
            dist[u] = INT_MAX;
    }
    dist[0] = INT_MAX;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        if (dist[u] < dist[0])
            for (int v:adj[u])
                if (dist[pairV[v]] == INT_MAX)
                {
                    dist[pairV[v]] = dist[u]+1;
                    Q.push(pairV[v]);
                }
    }
    return (dist[0] != INT_MAX);
}

bool HK_Dfs(int u)
{
    if (u != 0)
    {
        for (int v: adj[u])
            if (dist[pairV[v]] == dist[u]+1 && HK_Dfs(pairV[v]))
            {
                pairV[v] = u;
                pairU[u] = v;
                return true;
            }
        dist[u] = INT_MAX;
        return false;
    }
    return true;
}

int HopcroftKarp(int m, int n)
{
    for (int u=0; u<m; u++)
        pairU[u] = 0;
    for (int v=0; v<n; v++)
        pairV[v] = 0;
    int maxMatching = 0;

    while (HK_Bfs(m))
        for (int u=1; u<=m; u++)
            if (pairU[u]==0 && HK_Dfs(u))
                maxMatching++;
    return maxMatching;
}
//Maximal Matching ends

int main()
{
    int n, m;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>boysSkillz[i];
    cin>>m;
    for(int i=1;i<=m;i++)
        cin>>girlsSkillz[i];
    for(int i=1;i<=n;i++) //Building graph according to logic mentioned
        for(int j=1;j<=m;j++)
            if(abs(boysSkillz[i]-girlsSkillz[j])<=1)
            {
                adj[i].pb(j);
                adj[j].pb(i);
            }
    cout<<HopcroftKarp(n,m);
    return 0;
}

The input is as follows. 'n' is the number of boys. Then 'n' integers for their skills. 'm' is the number of girls. Then 'm' integers for their skill.

Eg:

4
1 4 6 2
5
5 1 5 7 9

The correct output for the input mentioned is 3. My code returns 4 which is wrong.

Everything in action: http://ideone.com/WOcE8I

Here's the link to the actual problem: http://codeforces.com/problemset/problem/489/B

Any help will be much appreciated

bholagabbar

The problem is in the second line of building the graph. We cannot have same indices of boys and girls being paired with each other. So the correct format would be:

adj[i].pb(j);
adj[j+n].pb(i); //This ensures indices assigned are distinct

This resolves the problem and should always be remembered while building a bipartite graph for max-matching

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

How can I optimize my java implementation of Held-Karp algorithm to shorten the running time?

From Dev

How do I concatenate my element id in this scenario?

From Dev

How do i optimise my for loop or better solution for this scenario?

From Dev

How do we solve the given scenario efficiently?

From Dev

How do I correctly publish my app?

From Dev

How do I correctly define my variables?

From Dev

How do I transpose my current range?

From Dev

How do you solve the given scenario with given memory constraints?

From Dev

How do I get the Type of a generic parameter for a given method

From Dev

How do I represent a graph given as an adjacency list in C#?

From Dev

How do I represent a graph given as an adjacency list in C#?

From Dev

Efficient trick for maximal bipartite matching in bigger graph

From Dev

Efficient trick for maximal bipartite matching in bigger graph

From Dev

How do I build in images to my app

From Dev

How do I use the Iterator trait to build generic APIs

From Dev

How do I use a generic method to build a list of same type?

From Dev

What is the role of Service layer in spring and how do I split my logic in this scenario?

From Dev

How do I "skip" a scenario with a tag in Cucumber?

From Dev

Eclipse ant build: how do I reference the current Eclipse path?

From Dev

Eclipse ant build: how do I reference the current Eclipse path?

From Dev

How can i pause program execution in the scenario given in description?

From Dev

How do I construct get the whole sub graph from a given resource in RDF Graph?

From Dev

How do I construct get the whole sub graph from a given resource in RDF Graph?

From Dev

How do I group my LINQ query correctly?

From Dev

How do I configure my project for Cocoa Pods correctly?

From Dev

How do I setup my CanCanCan permissions correctly?

From Dev

In Xcode how do I know if my lauch image is working correctly?

From Dev

How do i pass my scope correctly to look for variables

From Dev

How do I check my condition on an if statement to see if it is working correctly?

Related Related

  1. 1

    How can I optimize my java implementation of Held-Karp algorithm to shorten the running time?

  2. 2

    How do I concatenate my element id in this scenario?

  3. 3

    How do i optimise my for loop or better solution for this scenario?

  4. 4

    How do we solve the given scenario efficiently?

  5. 5

    How do I correctly publish my app?

  6. 6

    How do I correctly define my variables?

  7. 7

    How do I transpose my current range?

  8. 8

    How do you solve the given scenario with given memory constraints?

  9. 9

    How do I get the Type of a generic parameter for a given method

  10. 10

    How do I represent a graph given as an adjacency list in C#?

  11. 11

    How do I represent a graph given as an adjacency list in C#?

  12. 12

    Efficient trick for maximal bipartite matching in bigger graph

  13. 13

    Efficient trick for maximal bipartite matching in bigger graph

  14. 14

    How do I build in images to my app

  15. 15

    How do I use the Iterator trait to build generic APIs

  16. 16

    How do I use a generic method to build a list of same type?

  17. 17

    What is the role of Service layer in spring and how do I split my logic in this scenario?

  18. 18

    How do I "skip" a scenario with a tag in Cucumber?

  19. 19

    Eclipse ant build: how do I reference the current Eclipse path?

  20. 20

    Eclipse ant build: how do I reference the current Eclipse path?

  21. 21

    How can i pause program execution in the scenario given in description?

  22. 22

    How do I construct get the whole sub graph from a given resource in RDF Graph?

  23. 23

    How do I construct get the whole sub graph from a given resource in RDF Graph?

  24. 24

    How do I group my LINQ query correctly?

  25. 25

    How do I configure my project for Cocoa Pods correctly?

  26. 26

    How do I setup my CanCanCan permissions correctly?

  27. 27

    In Xcode how do I know if my lauch image is working correctly?

  28. 28

    How do i pass my scope correctly to look for variables

  29. 29

    How do I check my condition on an if statement to see if it is working correctly?

HotTag

Archive