I followed a tutorial here, to solve this question, where given solution is converted into bipartite graph and then calculating min path coverage in DAG.
I followed same approach, and I manually tested it, and it is working fine. but while submitting it, i am getting error.
Can you please check where I am going wrong? It won’t take long to understand this.
/* package codechef; // don't place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while(t-->0){
int n = in.nextInt();
int k = in.nextInt();
int p[][] = new int[k][n];
for(int i=0;i<k;i++){
for(int j=0;j<n;j++){
p[i][j] = in.nextInt();
}
}
HashMap<Integer, HashSet<Integer>> hm = new HashMap<Integer, HashSet<Integer>>();
for(int i=0;i<n;i++){
HashSet<Integer> al = new HashSet<Integer>();
for(int j=0;j<n;j++){
if(i!=j){
al.add(j);
}
}
hm.put(i,al);
}
for(int x=0;x<k;x++){
for(int i=0;i<n;i++){
HashSet<Integer> hs = hm.get(p[x][i]-1);
for(int j=i-1;j>=0;j--){
int v = p[x][j]-1;
hs.remove(v);
}
}
}
//removing extra edges
//It is DAG
//we need to calculate min path coverage with min individual paths total number(longest each path)
//Min path coverage in DAG = maximum bipartite matching
//Each elemtns in arraylist pointing to (+ to +) but change it to (+ to -)
for(int i=0;i<n;i++){
HashSet<Integer> hs = hm.get(i);
HashSet<Integer> hsN = new HashSet<Integer>();
for(int x: hs){
hsN.add(-x);
}
hm.put(i,hsN);
}
//bipartite graph created with edges going from positive set to negative set
int parent[] = new int[n];
for(int i=0;i<n;i++){
parent[i]=-1;
}
int minno = 0;
for(int i=0;i<n;i++){
boolean vis[] = new boolean[n];
for(int j=0;j<n;j++){
vis[j]=false;
}
dfs(i,parent,vis,hm);
}
int fromto[] = new int[n];
for(int i=0;i<n;i++){
fromto[i]=0;
}
for(int i=0;i<n;i++){
//System.out.print(parent[i]+" ");
if(parent[i]!=-1)
fromto[parent[i]]=i+1;
else
minno++;
}
System.out.println(minno);
for(int i=0;i<n;i++){
System.out.print(fromto[i]+" ");
}
System.out.println();
}
}
public static boolean dfs(int u, int parent[], boolean vis[], HashMap<Integer, HashSet<Integer>> hm){
HashSet<Integer> hs = hm.get(u);
for(int v: hs){
if(!vis[-v]){
vis[-v]=true;
if(parent[-v]!=-1){
if(dfs(-v,parent,vis,hm)){
parent[-v]=u;
return true;
}
}else{
parent[-v]=u;
return true;
}
}
}
return false;
}
}