import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; import java.util.Queue; import java.util.Set; import java.util.TreeSet; /* * * the most obvious solution: bipartite matching (with hopcroft-karp) * */ public class EgorHK { /** * @param args */ public static void main(String[] args) throws Exception { BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); int N=Integer.parseInt(reader.readLine()); int gSize=N*4+2; TreeSet[] graph=new TreeSet[gSize]; for(int i=0;i(); Map res2id=new HashMap(); long[][] equations=new long[N][]; for(int i=0;i[] getBfsTree(Set[] graph, int source, int target){ int n=graph.length; int[] used=new int[n]; Arrays.fill(used, -1); @SuppressWarnings("unchecked") Set[] result=new Set[n]; for(int i=0;i()); Queue q=new LinkedList(); used[source]=0; q.offer(source); while(!q.isEmpty()){ int current=q.poll(); if(current==target) return result; int currentDist=used[current]; for(int next:graph[current]){ if(used[next]==-1){ used[next]=currentDist+1; q.offer(next); } if(used[next]==currentDist+1) result[current].add(next); } } //no path to target: return null; } private boolean dfs(Set[] graph, Set[] bfsTree, int source, int target, boolean[] used){ if(source==target) return true; used[source]=true; for(int next: bfsTree[source]){ if(!used[next] && dfs(graph, bfsTree, next, target, used)){ graph[source].remove(next); graph[next].add(source); return true; } } return false; } //matching with hopcroft-karp O(m*sqrt(n)) public int matchingHopcroftKarp(Set[] graph, int source, int target){ int result=0; int n=graph.length; boolean[] used=new boolean[n]; while(true){ Set[] bfsTree=getBfsTree(graph, source, target); if(bfsTree==null) return result; Arrays.fill(used, false); while(dfs(graph, bfsTree, source, target, used)) result++; } } } }