JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums TopCoder Cookbook Algorithm Competitions - New Recipes Re: Solving Maximum Bipartite Matching Problem Revision History (21 edits)
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) Second way: Maximum flow algorithm.Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: S and T. We will create edges from S to all vertices of left part of graph and we will create edges from all vertices of right part of graph to T. All edges capacity will be equal to 1. After that we need to find maximum flow from S to T.All used edges between left and right parts are maximum matching. It is obvious why it works. It is easier to understand, especially if you understand and know how to code max flow algorithm.Implementation:```#include #include using namespace std;   class MaxFlowImplementation { public: vector > g; vector used; int n, k;   bool find_path(int a, int b) { if(a == b) return true; if(used[a]) return false; used[a] = true; for(int i = 0; i < n+k+2; i++) if(g[a][i] > 0 && find_path(i, b)) { g[a][i]--; g[i][a]++; return true; } return false; }   vector > find_max_matching(vector > &v, int _n, int _k) { //v[i] is a list of adjacent vertices to vertex i, where i is from left part and v[i][j] is from right part n = _n; //n is number of vertices in left part of graph k = _k; //k is number of vertices in right part of graph   g = vector >(n+k+2, vector(n+k+2)); //g[i][j] = 1 if there is edge between vertex i from left part // and vertex j from right part for(int i = 0; i < v.size(); i++) for(int j = 0; j < v[i].size(); j++) g[i][v[i][j]] = 1; int S = n+k; int T = n+k+1; for(int i = 0; i < n; i++) g[S][i] = 1; for(int i = 0; i < k; i++) g[n+i][T] = 1;   vector > _g(g);   used = vector (n+k+2, false); while(find_path(S, T)) fill(used.begin(), used.end(), false);   vector > res; for(int i = 0; i < n; i++) for(int j = n; j < n+k; j++) if(g[i][j] < _g[i][j]) res.push_back(make_pair(i, j));   return res; } }; ``` DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc. To tell the truth, while max - flow implementation is easier to understand and implement, Kuhn algorithm is more effective, especially improved implementation. Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem. We have numbers. Some pairs of these numbers are good. For example, we have {a, b, c, d}. Let good pairs be: (a,b) (b,c) (c,d). We need to select maximum amount of pairs so that no number to be in different pairs. Here they are (a,b) and (c,d).Of course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a2 + b2 = (some integer)2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; }   bool edge(int a, int b)//is there an edge between a and b? { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; }   int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums;//even numbers and then odd numbers(first n numbers are even, the rest are odd) for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack, here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or b.Implementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) Second way: Maximum flow algorithm.Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: S and T. We will create edges from S to all vertices of left part of graph and we will create edges from all vertices of right part of graph to T. All edges capacity will be equal to 1. After that we need to find maximum flow from S to T.All used edges between left and right parts are maximum matching. It is obvious why it works. It is easier to understand, especially if you understand and know how to code max flow algorithm.Implementation:```#include #include using namespace std;   class MaxFlowImplementation { public: vector > g; vector used; int n, k;   bool find_path(int a, int b) { if(a == b) return true; if(used[a]) return false; used[a] = true; for(int i = 0; i < n+k+2; i++) if(g[a][i] > 0 && find_path(i, b)) { g[a][i]--; g[i][a]++; return true; } return false; }   vector > find_max_matching(vector > &v, int _n, int _k) { //v[i] is a list of adjacent vertices to vertex i, where i is from left part and v[i][j] is from right part n = _n; //n is number of vertices in left part of graph k = _k; //k is number of vertices in right part of graph   g = vector >(n+k+2, vector(n+k+2)); //g[i][j] = 1 if there is edge between vertex i from left part // and vertex j from right part for(int i = 0; i < v.size(); i++) for(int j = 0; j < v[i].size(); j++) g[i][v[i][j]] = 1; int S = n+k; int T = n+k+1; for(int i = 0; i < n; i++) g[S][i] = 1; for(int i = 0; i < k; i++) g[n+i][T] = 1;   vector > _g(g);   used = vector (n+k+2, false); while(find_path(S, T)) fill(used.begin(), used.end(), false);   vector > res; for(int i = 0; i < n; i++) for(int j = n; j < n+k; j++) if(g[i][j] < _g[i][j]) res.push_back(make_pair(i, j));   return res; } }; ``` DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc. To tell the truth, while max - flow implementation is easier to understand and implement, Kuhn algorithm is more effective, especially improved implementation. Good example of using this algorithm in solving Topcoder Problem is PythTriplets ProblemOf course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a2 + b2 = (some integer)2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; }   bool edge(int a, int b)//is there an edge between a and b? { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; }   int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums;//even numbers and then odd numbers(first n numbers are even, the rest are odd) for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack, here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or b.Implementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) Second way: Maximum flow algorithm.Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: S and T. We will create edges from S to all vertices of left part of graph and we will create edges from all vertices of right part of graph to T. All edges capacity will be equal to 1. After that we need to find maximum flow from S to T.All used edges between left and right parts are maximum matching. It is obvious why it works. It is easier to understand, especially if you understand and know how to code max flow algorithm.Implementation:```#include #include using namespace std;   class MaxFlowImplementation { public: vector > g; vector used; int n, k;   bool find_path(int a, int b) { if(a == b) return true; if(used[a]) return false; used[a] = true; for(int i = 0; i < n+k+2; i++) if(g[a][i] > 0 && find_path(i, b)) { g[a][i]--; g[i][a]++; return true; } return false; }   vector > find_max_matching(vector > &v, int _n, int _k) { //v[i] is a list of adjacent vertices to vertex i, where i is from left part and v[i][j] is from right part n = _n; //n is number of vertices in left part of graph k = _k; //k is number of vertices in right part of graph   g = vector >(n+k+2, vector(n+k+2)); //g[i][j] = 1 if there is edge between vertex i from left part // and vertex j from right part for(int i = 0; i < v.size(); i++) for(int j = 0; j < v[i].size(); j++) g[i][v[i][j]] = 1; int S = n+k; int T = n+k+1; for(int i = 0; i < n; i++) g[S][i] = 1; for(int i = 0; i < k; i++) g[n+i][T] = 1;   vector > _g(g);   used = vector (n+k+2, false); while(find_path(S, T)) fill(used.begin(), used.end(), false);   vector > res; for(int i = 0; i < n; i++) for(int j = n; j < n+k; j++) if(g[i][j] < _g[i][j]) res.push_back(make_pair(i, j));   return res; } }; ``` DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc. To tell the truth, while max - flow implementation is easier to understand and implement, Kuhn algorithm is more effective, especially improved implementation. Good example of using this algorithm in solving Topcoder Problem is PythTriplets ProblemOf course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a2 + b2 = (some integer)2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack, here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or b.Implementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) Second way: Maximum flow algorithm.Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: S and T. We will create edges from S to all vertices of left part of graph and we will create edges from all vertices of right part of graph to T. All edges capacity will be equal to 1. After that we need to find maximum flow from S to T.All used edges between left and right parts are maximum matching. It is easier to understand (especially if you know how to code max flow algorithm) but it is slower than Kuhn's algorithm.Implementation:```#include #include using namespace std;   class MaxFlowImplementation { public: vector > g; vector used; int n, k;   bool find_path(int a, int b) { if(a == b) return true; if(used[a]) return false; used[a] = true; for(int i = 0; i < n+k+2; i++) if(g[a][i] > 0 && find_path(i, b)) { g[a][i]--; g[i][a]++; return true; } return false; }   vector > find_max_matching(vector > &v, int _n, int _k) { //v[i] is a list of adjacent vertices to vertex i, where i is from left part and v[i][j] is from right part n = _n; //n is number of vertices in left part of graph k = _k; //k is number of vertices in right part of graph   g = vector >(n+k+2, vector(n+k+2)); //g[i][j] = 1 if there is edge between vertex i from left part // and vertex j from right part for(int i = 0; i < v.size(); i++) for(int j = 0; j < v[i].size(); j++) g[i][v[i][j]] = 1; int S = n+k; int T = n+k+1; for(int i = 0; i < n; i++) g[S][i] = 1; for(int i = 0; i < k; i++) g[n+i][T] = 1;   vector > _g(g);   used = vector (n+k+2, false); while(find_path(S, T)) fill(used.begin(), used.end(), false);   vector > res; for(int i = 0; i < n; i++) for(int j = n; j < n+k; j++) if(g[i][j] < _g[i][j]) res.push_back(make_pair(i, j));   return res; } }; ``` DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc. To tell the truth, while max - flow implementation is easier to understand and implement, Kuhn algorithm is more effective, especially improved implementation. Good example of using this algorithm in solving Topcoder Problem is PythTriplets ProblemOf course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a2 + b2 = (some integer)2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack, here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or b.Implementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) Second way: Maximum flow algorithm.Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: S and T. We will create edges from S to all vertices of left part of graph and we will create edges from all vertices of right part of graph to T. All edges capacity will be equal to 1. After that we need to find maximum flow from S to T.All used edges between left and right parts are maximum matching.Implementation:```#include #include using namespace std;   class MaxFlowImplementation { public: vector > g; vector used; int n, k;   bool find_path(int a, int b) { if(a == b) return true; if(used[a]) return false; used[a] = true; for(int i = 0; i < n+k+2; i++) if(g[a][i] > 0 && find_path(i, b)) { g[a][i]--; g[i][a]++; return true; } return false; }   vector > find_max_matching(vector > &v, int _n, int _k) { //v[i] is a list of adjacent vertices to vertex i, where i is from left part and v[i][j] is from right part n = _n; //n is number of vertices in left part of graph k = _k; //k is number of vertices in right part of graph   g = vector >(n+k+2, vector(n+k+2)); //g[i][j] = 1 if there is edge between vertex i from left part // and vertex j from right part for(int i = 0; i < v.size(); i++) for(int j = 0; j < v[i].size(); j++) g[i][v[i][j]] = 1; int S = n+k; int T = n+k+1; for(int i = 0; i < n; i++) g[S][i] = 1; for(int i = 0; i < k; i++) g[n+i][T] = 1;   vector > _g(g);   used = vector (n+k+2, false); while(find_path(S, T)) fill(used.begin(), used.end(), false);   vector > res; for(int i = 0; i < n; i++) for(int j = n; j < n+k; j++) if(g[i][j] < _g[i][j]) res.push_back(make_pair(i, j));   return res; } }; ``` DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc. To tell the truth, while max - flow implementation is easier to understand and implement, Kuhn algorithm is more effective, especially improved implementation. Good example of using this algorithm in solving Topcoder Problem is PythTriplets ProblemOf course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a2 + b2 = (some integer)2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack, here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or b.Implementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) Second way: Maximum flow algorithm.Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: S and T. We will create edges from S to all vertices of left part of graph and we will create edges from all vertices of right part of graph to T. All edges capacity will be equal to 1. After that we need to find maximum flow from S to T.All used edges between left and right parts are maximum matching.Implementation:```#include #include using namespace std;   class MaxFlowImplementation { public: vector > g; vector used; int n, k;   bool find_path(int a, int b) { if(a == b) return true; if(used[a]) return false; used[a] = true; for(int i = 0; i < n+k+2; i++) if(g[a][i] > 0 && find_path(i, b)) { g[a][i]--; g[i][a]++; return true; } return false; }   vector > find_max_matching(vector > &v, int _n, int _k) { //v[i] is a list of adjacent vertices to vertex i, where i is from left part and v[i][j] is from right part n = _n; //n is number of vertices in left part of graph k = _k; //k is number of vertices in right part of graph   g = vector >(n+k+2, vector(n+k+2)); //g[i][j] = 1 if there is edge between vertex i from left part // and vertex j from right part for(int i = 0; i < v.size(); i++) for(int j = 0; j < v[i].size(); j++) g[i][n+v[i][j]] = 1; int S = n+k; int T = n+k+1; for(int i = 0; i < n; i++) g[S][i] = 1; for(int i = 0; i < k; i++) g[n+i][T] = 1;   vector > _g(g);   used = vector (n+k+2, false); while(find_path(S, T)) fill(used.begin(), used.end(), false);   vector > res; for(int i = 0; i < n; i++) for(int j = n; j < n+k; j++) if(g[i][j] < _g[i][j]) res.push_back(make_pair(i, j));   return res; } }; ``` DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc. To tell the truth, while max - flow implementation is easier to understand and implement, Kuhn algorithm is more effective, especially improved implementation. Good example of using this algorithm in solving Topcoder Problem is PythTriplets ProblemOf course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a2 + b2 = (some integer)2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack, here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or b.Implementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) Second way: Maximum flow algorithm.Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: S and T. We will create edges from S to all vertices of left part of graph and we will create edges from all vertices of right part of graph to T. All edges capacity will be equal to 1. After that we need to find maximum flow from S to T.All used edges between left and right parts are maximum matching.Implementation:```#include #include using namespace std;   class MaxFlowImplementation { public: vector > g; vector used; int n, k;   bool find_path(int a, int b) { if(a == b) return true; if(used[a]) return false; used[a] = true; for(int i = 0; i < n+k+2; i++) if(g[a][i] > 0 && find_path(i, b)) { g[a][i]--; g[i][a]++; return true; } return false; }   vector > find_max_matching(vector > &v, int _n, int _k) { //v[i] is a list of adjacent vertices to vertex i, where i is from left part and v[i][j] is from right part n = _n; //n is number of vertices in left part of graph k = _k; //k is number of vertices in right part of graph   g = vector >(n+k+2, vector(n+k+2)); //g[i][j] = 1 if there is edge between vertex i from left part // and vertex j from right part for(int i = 0; i < v.size(); i++) for(int j = 0; j < v[i].size(); j++) g[i][n+v[i][j]] = 1; int S = n+k; int T = n+k+1; for(int i = 0; i < n; i++) g[S][i] = 1; for(int i = 0; i < k; i++) g[n+i][T] = 1;   vector > _g(g);   used = vector (n+k+2, false); while(find_path(S, T)) fill(used.begin(), used.end(), false);   vector > res; for(int i = 0; i < n; i++) for(int j = n; j < n+k; j++) if(g[i][j] < _g[i][j]) res.push_back(make_pair(i, j));   return res; } }; ``` DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets ProblemOf course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a2 + b2 = (some integer)2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack, here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or b.Implementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) Second way: Maximum flow algorithm.Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.All used edges between left and right parts are maximum matching.Implementation:```#include #include using namespace std;   class MaxFlowImplementation { public: vector > g; vector used; int n, k;   bool find_path(int a, int b) { if(a == b) return true; if(used[a]) return false; used[a] = true; for(int i = 0; i < n+k+2; i++) if(g[a][i] > 0 && find_path(i, b)) { g[a][i]--; g[i][a]++; return true; } return false; }   vector > find_max_matching(vector > &v, int _n, int _k) { //v[i] is a list of adjacent vertices to vertex i, where i is from left part and v[i][j] is from right part n = _n; //n is number of vertices in left part of graph k = _k; //k is number of vertices in right part of graph   g = vector >(n+k+2, vector(n+k+2)); //g[i][j] = 1 if there is edge between vertex i from left part // and vertex j from right part for(int i = 0; i < v.size(); i++) for(int j = 0; j < v[i].size(); j++) g[i][n+v[i][j]] = 1; int A = n+k; int B = n+k+1; for(int i = 0; i < n; i++) g[A][i] = 1; for(int i = 0; i < k; i++) g[n+i][B] = 1;   vector > _g(g);   used = vector (n+k+2, false); while(find_path(A, B)) fill(used.begin(), used.end(), false);   vector > res; for(int i = 0; i < n; i++) for(int j = n; j < n+k; j++) if(g[i][j] < _g[i][j]) res.push_back(make_pair(i, j));   return res; } }; ``` DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets ProblemOf course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack, here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or bImplementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets ProblemOf course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack, here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or bImplementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets ProblemOf course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack (http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or bImplementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets ProblemOf course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack (http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or bImplementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem in SRM 477(http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157).Of course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```Another good example of using this algorithm is problem RookAttack (http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or bImplementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   //if you use Kuhn algorithm KuhnImplementation obj; // or if you use max flow algorithm //MaxFlowImplementation obj return obj.find_max_matching(g, n, k).size(); } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem in SRM 477(http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157).Of course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; long long sqr = (long long)(sqrt((double)(n))+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j);   //if you use Kuhn algorithm MyClass obj; return obj.find_max_matching(g, n, k).size(); // or if you use max flow algorithm /* */ } ```Another good example of using this algorithm is problem RookAttack (http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or bImplementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   MyClass obj; return obj.find_max_matching(g, n, k).size();   } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem in SRM 477(http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157).Of course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; double sq = sqrt((double)(n)); long long sqr = (long long)(sq+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   //if you use Kuhn algorithm vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j); /* //if you use max flow algorithm vector > g; for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g.push_back(make_pair(i, j));*/ MyClass obj; return obj.find_max_matching(g, n, k).size(); } ```Another good example of using this algorithm is problem RookAttack (http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any vertices of a or bImplementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   MyClass obj; return obj.find_max_matching(g, n, k).size();   } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem in SRM 477(http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157).Of course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; double sq = sqrt((double)(n)); long long sqr = (long long)(sq+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   //if you use Kuhn algorithm vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j); /* //if you use max flow algorithm vector > g; for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g.push_back(make_pair(i, j));*/ MyClass obj; return obj.find_max_matching(g, n, k).size(); } ```Another good example of using this algorithm is problem RookAttack (http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks.So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge a-b, we can't use edges which has any edge of a or bImplementation:```class RookAttack { public: int howMany(int n, int k, vector cuts) { vector > g(n); vector > _g(n, vector (k, true)); for(int i = 0; i < cuts.size(); i++) { istringstream is(cuts[i]); int a, b; char c; while(is >> a >> b) { _g[a][b] = false; is >> c; } }   for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) if(_g[i][j]) g[i].push_back(j+n);   MyClass obj; return obj.find_max_matching(g, n, k).size();   } }; ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem in SRM 477(http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157).Of course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; double sq = sqrt((double)(n)); long long sqr = (long long)(sq+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   //if you use Kuhn algorithm vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j); /* //if you use max flow algorithm vector > g; for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g.push_back(make_pair(i, j));*/ MyClass obj; return obj.find_max_matching(g, n, k).size(); } ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem in SRM 477(http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157).Of course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all add numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; double sq = sqrt((double)(n)); long long sqr = (long long)(sq+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   //if you use Kuhn algorithm vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j); /* //if you use max flow algorithm vector > g; for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g.push_back(make_pair(i, j));*/ MyClass obj; return obj.find_max_matching(g, n, k).size(); } ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem in SRM 477(http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157).Of course first you need to do is build a graph. Each vertex is a number(unique). After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all add numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:```class PythTriplets { public: int gcd(int a, int b) { return b?gcd(b, a%b):a; } bool edge(int a, int b) { long long _a = a, _b = b, n = _a*_a + _b*_b; double sq = sqrt((double)(n)); long long sqr = (long long)(sq+1e-9); if(sqr*sqr != n) return false; return gcd(a, b) == 1; } int findMax(vector stick) { string s; for(int i = 0; i < stick.size(); i++) s += stick[i];   vector v; istringstream is(s); int a; while(is >> a) v.push_back(a);   vector nums; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 0) nums.push_back(v[i]); int n = nums.size(), k = v.size() - n; for(int i = 0; i < v.size(); i++) if(v[i]%2 == 1) nums.push_back(v[i]);   //if you use Kuhn algorithm vector > g(nums.size()); for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g[i].push_back(j); /* //if you use max flow algorithm vector > g; for(int i = 0; i < v.size(); i++) for(int j = i+1; j < v.size(); j++) if(edge(nums[i], nums[j])) g.push_back(make_pair(i, j));*/ MyClass obj; return obj.find_max_matching(g, n, k).size(); } ```
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem in SRM 477(http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157).Of course first you need to do is build a graph. Each vertex is a number(unique). After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all add numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.After that we just find maximum matching and return it's size:
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem in SRM 477(http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157).Of course first you need to do is build a graph. Each vertex is a number(unique). After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First way is to notice that if we place all even numbers to left part and all add numbers to right part then we will get a bipartite graph. How to prove it?First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way is to build a bipartite graph using algorithm.We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem in SRM 477(http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157).Of course first you need to do is build a graph. Each vertex is a number(unique). After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here. First is to notice that if we place all even numbers to left part and all add numbers to right part then we will get a bipartite graph. How to prove it? First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because(2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).Second way to build a bipartite graph is to use algorithm.we will go through vertices and call dfs() from unused vertices and place them to left part, its neighbors to right part and so on.
 Re: Solving Maximum Bipartite Matching Problem (response to post by ibra) DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem in SRM 477(http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157).Of course first you need to do is build a graph. The trick is that it is a bipartite graph. Each vertex is a number(unique). After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^2 + b^2 = (some integer)^2).