bipartite matching in C++, what is wrong in my code?

Question

I have worked on a bipartite matching problem, and I obviously got a trouble to solve it.

Let me tell you what the problem is about.

As an input form, it gives me N, M which is the number of people at the work and the number of different kind of jobs in the work. In the following N lines, it tells us s that tells how many kind of job that ith person can do. In the following s numbers, they will tell us that which jobs can ith person can do. The number of the jobs si will satisfy 1<=si<=M. Then, if each person can work on only one or less job at a time, how many jobs can be done at most?

This is the problem, and I hope this made sense for you;) I apologize my poor english skill. Returning to the point, this is my code.

#include <stdio.h>

int n, m, dfscheck[1003], check[1003], input[1003][1003], back[1003], tmp, count=0;

void dfs(int num)
{
    int i, j;
    if(check[num]==0)
    {
        tmp=-1;
        check[num]=1;
        return;
    }
    if(dfscheck[num]==1)
        return;
    dfscheck[num]=1;
    for(j=1; j<=input[back[num]][0]; j++)
    {
        dfs(input[back[num]][j]);
        if(tmp==-1)
        {
            back[input[back[num]][j]]=back[num];
            return;
        }
    }
}

int main(void)
{
    int i, j, flag ,k;
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++)
    {
        scanf("%d", &input[i][0]);
        for(j=1; j<=input[i][0]; j++)
            scanf("%d", &input[i][j]);
    }
    for(i=1; i<=n; i++)
    {
        flag=0;
        for(j=1; j<=input[i][0]; j++)
            if(check[input[i][j]]==0)
            {
                check[input[i][j]]=1;
                count++;
                flag=1;
                back[input[i][j]]=i;
                break;
            }

        if(flag==0)
            for(j=1; j<=input[i][0]; j++)
            {
                for(k=0; k<=1001; k++)
                    dfscheck[k]=0;
                tmp=0;
                dfs(input[i][j]);
                if(tmp==-1)
                {
                    back[input[i][j]]=i;
                    count++;
                }
            }
    }
    printf("%d", count);
    return 0;
}

The name of tmp is really bad to understand code, so... tmp works like a flag in the function dfs. It tells whether it has found a matching.

I got wrong answer, neither runtime error nor time exceed. I have read several different codes that others have written, and I couldn't find which part is wrong in my code.

I have found that my code is distinct from others' in the part that I don't define a array, A[i], showing which job is matched to ith person, exactly opposite to Back array in my code. As far as I understood their codes, the purpose of it is to find out ith person has already been matched before we get into dfs. I don't think this case can be happened. Since no flow has come out of the node of ith person, it is impossible for a flow to go from a node of jobs to the node in max flow.

I wanted to say my thoughts even if it is useless, just in case that it helps you give me some advices. Anyway, let me have your opinions!!! Thank you so much for your time.

Answer 1

One thing that looks weird is:

            if(tmp==-1)
            {
                back[input[i][j]]=i;
                count++;
                // I would expect to see "break;" here
            }

if you find a way to assign person i to a job you increment the count, and then carry on trying to see if you can find an alternative way to assign the same person. This means that you may end up assigning the same person to multiple jobs!

I recommend inserting a "break;" statement once you have found a job for the person.