1. Definition of bipartite graph
A bipartite graph is a special undirected graph whose nodes can be divided into two disjoint sets, so that there are no edges connecting any two nodes in the same set, but there are no edges between nodes in different sets. Connected by edges.
In other words, if an undirected graph can be divided into two sets, and the two endpoints of all edges belong to different sets, then the undirected graph is a bipartite graph.
As shown in the figure, there are two sets, blue and green. Points in the set can be connected to points in the other set, but cannot be connected within the set. This is called a bipartite graph.
So how to determine whether it is a bipartite graph? This requires the use of bipartite graph coloring
2. Coloring of bipartite graphs
Assuming that the colors in the picture have not been marked, only points and edges, then we need to color the points that can be directly reached by each point (that is, the points in different sets are dyed with different colors). If it can meet the “different colors of adjacent points” “This condition is a bipartite graph.
On the contrary, as follows, there is a connecting line between two blue points, but they are the same color, so the condition cannot be met.
Example 1
1. Use vector to build a map. At this time, we already know all the adjacent points of each point (recorded as point i) (that is, the points that can be reached by walking only one edge). Then the color of the adjacent point j of point i cannot be Same as dot i
2. If point i is blue, point j should be dyed green
3. We want to take point i as the starting point and traverse all reachable points. We can use dfs or bfs.
4. If a certain point is not dyed during the dyeing process, dye it to the opposite color;
If it has been dyed and the color is the opposite color, do not worry;
If it has been dyed and has the same color, it means that the condition is not met and this is not a bipartite graph.
dfs writing method
#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647
#define int long long
//#include <bits/stdc + + .h>
typedef long long ll;
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }
vector<int> edge[N];
int vis[N];//0 is blue, 1 is green
bool ans = true;
void dfs(int cur, int c) {
//Function: Traverse the points that cur can reach and color these points
vis[cur] = c;
for (auto x : edge[cur]) {
//Traverse the adjacent points of cur
if (vis[x] == -1) {
//Not yet dyed
dfs(x, 1 - c);
//Dye the x point into a different color than cur
//And start a deep search
}
else if (vis[x] == vis[cur]) {
ans = false;
}
}
}
signed main() {
memset(vis, -1, sizeof vis);
int n, m; cin >> n >> m;
while (m--) {
int a, b; cin >> a >> b;
edge[a].push_back(b);
edge[b].push_back(a);
}
for (int i = 1; i <= n; i + + ) {
if (vis[i] == -1) dfs(i, 1);
}
if (ans) cout << "Yes";
else cout << "No";
return 0;
}
bfs writing method
#include<assert.h>
#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647
#define int long long
//#include <bits/stdc + + .h>
typedef long long ll;
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }
vector<int> edge[N];
int vis[N];//0 is blue, 1 is green
bool ans = true;
void bfs(int cur) {
//Function: Traverse the points that cur can reach and color these points
\t
queue<int> q;
q.push(cur);
vis[cur] = 0;
while (!q.empty()) {
int t = q.front();
\t\t
q.pop();
for (auto x : edge[t]) {
if (vis[x] == -1) {
q.push(x);
vis[x] = 1 - vis[t];
}
else if (vis[x] == vis[t]) {
ans = false;
return;
}
}
}
}
signed main() {
memset(vis, -1, sizeof vis);
int n, m; cin >> n >> m;
while (m--) {
int a, b; cin >> a >> b;
edge[a].push_back(b);
edge[b].push_back(a);
}
for (int i = 1; i <= n; i + + ) {
if (vis[i] == -1) bfs(i);
}
if (ans) cout << "Yes";
else cout << "No";
return 0;
}
Example 2
D – Good Tuple Problem
Analysis: Atcoder’s weekly competition is basically a template question
#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647
#define int long long
//#include <bits/stdc + + .h>
typedef long long ll;
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }
vector<int> dif[N];//dif[i] stores nodes that need to be different from the i node
int a[N], b[N], x[N];
bool ans = true;
void dfs(int i, int s) {
x[i] = s;
for (int j = 0; j < dif[i].size(); j + + ) {
if (x[dif[i][j]] == -1) {
dfs(dif[i][j], 1 - s);
}
else if (x[dif[i][j]] == x[i]) ans = false;
}
}
signed main() {
int n, m; cin >> n >> m;
for (int i = 0; i < m; i + + ) {
cin >> a[i];
}
for (int i = 0; i < m; i + + ) {
cin >> b[i];
}
for (int i = 0; i < m; i + + ) {
dif[a[i]].push_back(b[i]);
dif[b[i]].push_back(a[i]);
}
memset(x, -1, sizeof x);
for (int i = 1; i <= n; i + + ) {
if(x[i]==-1) dfs(i, 0);
}
if (ans) cout << "Yes";
else cout << "No";
return 0;
}
Block Sunshine University
Enter #1Copy
3 3 1 2 1 3 twenty three
Output #1Copy
Impossible
Enter #2Copy
3 2 1 2 twenty three
Output #2Copy
1
Analysis: This question examines Coloring of bipartite graphs
It is easier to know that this question is about bipartite graph coloring.
First we have to consider how to place the crabs. In order for all roads to be blocked, the following conditions need to be met:
1. Among the two points connected by each edge, one of the two points must be selected.
2. Among the two points connected by each edge, two points cannot be selected at the same time (otherwise the crab will be disharmonious)
Suppose there is a graph now, and the following two are subconnected graphs of this graph.
If there is such a subconnected graph, the least number of crabs we place is two, that is, the number of nodes dyed blue
If there is such a sub-connected graph, then the number of crabs placed is two, that is, the number of red nodes
A graph is composed of multiple sub-connected graphs. Find the optimal number of placements for each sub-connected graph, and then add them up to get the final answer.
Therefore we can use bipartite graph coloring.
In the check function, each time it passes through dfs, it means dyeing a sub-connected graph. Then you only need to record the number of nodes of different colors in dfs once, and add the smaller number to ans.
#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647
#define int long long
//#include <bits/stdc + + .h>
typedef long long ll;
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }
int cnt = 0;
int head[N], e[N], ne[N];
int vis[N];
void add(int u, int v) {
e[cnt] = v, ne[cnt] = head[u], head[u] = cnt + + ;
}
int n, m;
int ans;
int cnt_0, cnt_1;
bool dfs(int x, int c) {
vis[x] = c;
if (c == 0) cnt_0 + + ;
else cnt_1 + + ;
for (int i = head[x]; i != -1; i = ne[i]) {
int j = e[i];
if (vis[j] == -1) dfs(j, 1 - c);
else if (vis[j] == vis[x]) return false;
}
return true;
}
bool check() {
for (int i = 1; i <= n; i + + ) {
//Start from each point for coloring
if (vis[i] == -1) {
cnt_0 = cnt_1 = 0;
if (!dfs(i, 1)) return false;
ans + = min(cnt_0, cnt_1);
}
}
return true;
}
signed main() {
cin >> n >> m;
memset(vis, -1, sizeof vis);
memset(head, -1, sizeof head);
for (int i = 0; i < m; i + + ) {
int u, v; cin >> u >> v;
add(u, v), add(v, u);
}
if (check()) {
cout << ans;
}
else {
cout << "Impossible";
}
return 0;
}
3.Hungarian algorithm
The Hungarian algorithm is used to find the maximum matching number of a bipartite graph. Pay attention! is the maximum number of matches and is unrightted
Suppose there are these boys and girls, and the boy likes some girls, and asks how to match them so that the number of matched couples can be maximized.
Answer: We regard the following behavior as a “chasing” action
The boy i visits the girls he likes one by one. If the girl j does not have a partner yet, the match will be successful.
If girl j has a partner, that is, the boy match[j], then go and see if the boy match[j] can change his girlfriend (that is, girl j has room for adjustment), and then give girl j to boy i. If so, boy i also matches successfully.
If boy i has gone through all the girls he likes and still cannot find it, the match will fail.
Let’s focus on explaining st[]. The function is not to visit the same girl repeatedly, causing the recursion to fall into an infinite loop.
We can think of the role of st[] as a “booking” behavior. When girl j has not been booked yet, she will be booked, that is, st[j] = true, to see if this girlfriend can be chased (also That’s the part I “answered” above). If not, go look for other girls you like.
Attention! Regardless of whether the girl pursues him or not, she has already been “booked” and cannot be visited again in the future.
So how did it end up in an infinite loop?
If there is no st array, the situation is as follows.
When boy i visits girl j, and girl j already has boy k as her boyfriend, then it is time to see if boy k can change to another girlfriend. So boy K will go through all the girls he likes to see if there are any girls who have not been selected, or girls who have room for adjustment.
Here’s the problem! In this case, boy k may visit girl j again, and then see if girl j has room for adjustment, that is, whether he has room for adjustment, and fall into a recursive infinite loop!
Therefore, the existence of st[] is necessary.
#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647
#define int long long
//#include <bits/stdc + + .h>
typedef long long ll;
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }
int cnt = 0;
int head[N], e[N], ne[N];
int match[N];
bool st[N];
void add(int u, int v) {
e[cnt] = v, ne[cnt] = head[u], head[u] = cnt + + ;
}
bool find(int x) {
//Find if x can match with a girlfriend
\t
//Traverse the girls that x likes
for (int i = head[x]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
st[j] = true;
if (match[j]==0 || find(match[j])) {
//If girl j does not have a boyfriend, or the girl's current boyfriend can choose another girl
//Then let the boy find another girl, and boy x matches girl j
match[j] = x;
return true;
}
}
}
return false;
}
int a, b, n;
signed main() {
memset(head, -1, sizeof head);
cin >> a >> b >> n;
for (int i = 0; i < n; i + + ) {
int u, v, w; cin >> u >> v;
add(u, v);
}
int ans = 0;
for (int i = 1; i <= a; i + + ) {
memset(st, false, sizeof st);
if (find(i)) ans + + ;
}
cout << ans;
return 0;
}