The code can be found here: https://sites.google.com/site/indy256/algo/kuhn_matching2
More specifically, I'm not sure I understand what the int n2 is for and how it is being used.
Here, for bipartite graphs, n1 denotes number of vertices of the first set (partition) and n2 denotes number of vertices of the second set. E.g. you would have a set of workers and a set of tasks they would perform. In the example above, there are 2 workers (say John=0 and Bob=1) and three tasks (say, coding=0, QA=1, support=2). John can do coding and support. Bob can do only support. None of them can do QA (there is no g[i] == 1)
Then the algorithm follows Kuhn's proposal to find a maximum matching (do not confuse with maximal matching). In our example case, maximum matching has two edges (e.g. John->coding and Bob->support).
The algorithm above would not work for weighted bipartite graphs.
Update
To accommodate the input rules from the question, following needs to be done. Simpy ensure that in g[x]=y : 0 <= x < n1 and 0 <= y < n2
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n1 = sc.nextInt();
int n2 = sc.nextInt();
int m = sc.nextInt();
LinkedList<Integer>[] g = new LinkedList[n1];
for (int j = 0; j < n1; j++) {
g[j] = new LinkedList<Integer>();
}
int i = 0;
while(i != m){
int v = sc.nextInt();
int v2 = sc.nextInt();
if(v>=1 && v<=n1) {
//v belongs in first set
g[v-1].add(v2-n1-1);
}else if(v>=n1+1 && v<=n1+n2) {
//v belongs in the second set, v2 into the first
g[v2-1].add(v-n1-1);
}
i++;
}
System.out.println(maxMatching(g, n2));
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments