# Acwing-Algorithm Basic Course-Notes (9)

## Search and Graph Theory (3)

This section explains the minimum spanning tree and bipartite graph

### Minimum spanning tree

What is the minimum spanning tree? 1. given an undirected connected graph G with n nodes and m edges.

Then the undirected connected graph composed of all n nodes and n-1 edges is called a spanning tree of G. Among all spanning trees of G, the spanning tree with the smallest sum of edge weights is It is called the minimum spanning tree of G.

There are two common algorithms:

• Prim algorithm (prime)

• Simple version of Prim (time complexity O(n^2^), suitable for dense graphs)
• Heap optimized version Prim (time complexity O(mlogn), suitable for sparse graphs)
• Kruskal algorithm (Kruskal)

Suitable for sparse graphs, time complexity O(mlogm)

For the minimum spanning tree problem, if it is a dense graph, the naive Prim algorithm is usually used because its idea is simpler and the code is shorter. If it is a sparse graph, the Kruskal algorithm is usually used because its idea is simpler and clearer than Prim. The heap optimized version of Prim is usually not used much.

#### Prim algorithm

Here only talk about the plain version of Prim. The algorithm flow is as follows

(Where the collection

s
Indicates that all points currently in the connected block)

```1. Initialize the distance, initialize the distance of all points to +
2. n cycles
1. t <- find the closest point that is not in the set s
2. Use t to update the distance from other points to the set s
3. Add t to the set s
Copy code```

Note that the distance from a point t to the set s refers to if the point t and three points in the set s are connected by an edge. Then the distance from the point t to the set s is the weight of the edge with the smallest weight among the edges where t is connected to the 3 points.

Practice picture: acwing-858: Prim algorithm for minimum spanning tree

Solution: (C++)

```# include <iostream>
# include <cstring>
using  namespace  std ;
const  int N = 510 , INF = 0x3f3f3f3f ;
int n, m;
int g[N][N], d[N];
bool visited[N];

void  prim ()  {
memset (d, 0x3f , sizeof d);//Initialization distance is positive infinity
int sum = 0 ;
for ( int i = 1 ; i <= n; i++) {
//loop n times
//choose The point with the smallest distance set s
int t = 0 ;
for ( int j = 1 ; j <= n; j++) {
if (!visited[j] && d[j] <= d[t]) t = j;//Use <= here to avoid making special judgments on the first point selection
}
if (i == 1 ) d[t] = 0 ; //The first point added to the set, the distance to the set is 0
if (d[t] ==  INF) {
//The distance of the selected point is positive infinity , Invalid
printf ( "impossible\n" );
return ;
}
//Put this point in the set s
visited[t] = true ;
sum += d[t]; //This time I put it in
//Update the distance from other points to the set s,
for ( int j = 1 ; j <= n; j++) {
if (!visited[j] && g [t][j] != INF && g[t][j] <d[j]) {
d[j] = g[t][j];
}
}
}
printf ( "%d\n" , sum);
}

int  main ()  {
memset (g, 0x3f , sizeof g);
scanf ( "%d%d" , &n, &m);
while (m--) {
int x, y, w;
scanf ( "%d%d %d" , &x, &y, &w);
g[x][y] = min(g[x][y], w);
g[y][x] = g[x][y];
}
prim();
return  0 ;
}
Copy code```

Solution: (Java)

```import java.util.Scanner;

/**
* @Author yogurtzzz
* @Date 2021/6/28 16:43
**/
public  class  Main  {

static  int INF = 0x3f3f3f3f ;

static Scanner scanner = new Scanner(System.in);

public  static  void  main (String[] args)  {
int n = readInt(), m = readInt();
int [][] g = new  int [n + 1 ][n + 1 ];
for ( int i = 1 ; i <= n; i++)
for ( int j = 1 ; j <= n; j++) g[i][j] = INF;
while (m--> 0 ) {
int u = readInt(), v = readInt(), w = readInt();
g[v][u] = g[u][v] = Math.min(g[u][v], w); //undirected graph, with two edges
}
int res = prim(g, n);
if (res == INF) System.out.println( "impossible" );
else System.out.println(res);
}

static  int  prim ( int [][] g, int n)  {
int [] d = new  int [n + 1 ];
boolean [] st = new  boolean [n + 1 ];
for ( int i = 0 ; i < n + 1 ; i++) d[i] = INF;

int sum = 0 ; //The
sum of the edge weights of the minimum spanning tree //loop n times, each time selecting a point that is not in the set s, but the smallest distance to the set s
for ( int i = 1 ; i <= n; i++ ) {
//Traverse, find a point that is not in s and has the smallest distance
int t = 0 ;
for ( int j = 1 ; j <= n; j++) {
if (!st[j] && d[j] < = d[t]) t = j;
}
if (i == 1 ) d[t] = 0 ; //The first selected point, the distance should be 0
if (d[t] ==  INF) return INF; //If the selected point is to the set The distance is positive infinity, it means that there is no connection
sum += d[t]; //add this edge to the spanning tree
st[t] = true ; //add point t to the set s
//update other points to the set Distance, update only the edges connected to t
for ( int j = 1 ; j <= n; j++) {
if (!st[j] && g[t][j] != INF && d[j]> g[ t][j]) {
d[j] = g[t][j];
}
}
}
return sum;
}

static  int  readInt ()  {
return scanner.nextInt();
}
}
Copy code```

#### Kruskal algorithm

The basic idea:

1. First sort all edges according to weight, from small to large

2. Enumerate each edge from small to large (a, b, w)

If a and b are not connected, add this edge to the set (connect point a and point b)

At the beginning of Kruskal's algorithm, it is equivalent to all points are independent, without any edges.

Kruskal does not need to use an adjacency list or adjacency matrix to store the graph, it only needs to store all the edges.

In fact, it is a simple application of union search, you can refer to acwing-837: the number of points in connected blocks

Practice questions: acwing-859: Kruskal algorithm for minimum spanning tree

Solution: (C++)

```# include <iostream>
# include <cstring>
# include <algorithm>
using  namespace  std ;
const  int N = 1e5 + 10 , M = 2e5 + 10 ;

struct  Edge {
int a, b, w;
bool  operator <( const Edge& W) {
return w <Ww;
}
} edges[M];

int n, m;
int p[N];

int  find ( int x)  {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}

void  kruskal ()  {
//Sort all edges from smallest to largest first
sort(edges, edges + m);
int totalW = 0 , edgeCtn = 0 ;
//enumerate all edges
for ( int i = 0 ; i <m; i++) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a);
b = find(b);
if (a != b) {
//If a and b are not connected, add this edge
p[a] = b; //connect a and b
totalW += w;
edgeCtn++;
}
}
if (edgeCtn == n- 1 ) printf ( "%d\n" , totalW);
else  printf ( "impossible\n" );
}

int  main ()  {
scanf ( "%d%d" , &n, &m);
for ( int i = 0 ; i <m; i++) {
int a, b, w;
scanf ( "%d%d%d" , &a, &b, &w);
edges[i] = {a, b, w};
}

for ( int i = 1 ; i <= n; i++) p[i] = i;

kruskal();

return  0 ;
}
Copy code```

Solution: (Java)

```import java.util.Arrays;
import java.util.Scanner;

/**
* @Author yogurtzzz
* @Date 2021/6/30 16:42
**/
public  class  Main  {
static  class  Edge  implements  Comparable < Edge > {

int a, b, w;

public  Edge ( int a, int b, int w)  {
this .a = a;
this .b = b;
this .w = w;
}

@Override
public  int  compareTo (Edge o)  {
return w-ow;
}
}

static Scanner scanner = new Scanner(System.in);

public  static  void  main (String[] args)  {
int n = readInt(), m = readInt();
Edge[] edges = new Edge[m];
int [] p = new  int [n + 1 ];
for ( int i = 0 ; i <m; i++) {
int a = readInt(), b = readInt() , w = readInt();
edges[i] = new Edge(a, b, w);
}
//Initialize all points are isolated
for ( int i = 1 ; i <= n; i++) p[i] = i;
kruskal(edges, n, m, p);
}

static  void  kruskal (Edge[] edges, int n, int m, int [] p)  {
//1. 1. sort all edges according to the weight from small to large
Arrays.sort(edges);
int totalWeight = 0 , edgeCtn = 0 ;
//2. Traverse all edges
for ( int i = 0 ; i <m; i++) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a, p);
b = find(b, p);
if (a != b) {
//a and b are not connected yet, then connect
p[a] = b;
totalWeight += w;
edgeCtn++;
}
}
//If there is a minimum spanning tree, the total number of edges added is n-1
if (edgeCtn == n- 1 ) System.out.println(totalWeight);
else System.out.println( "impossible" );
}

static  int  find ( int x, int [] p)  {
if (x != p[x]) p[x] = find(p[x], p);
return p[x];
}

static  int  readInt ()  {
return scanner.nextInt();
}
}
Copy code```

### binary picture

First of all, what is a bipartite graph?

A bipartite graph means that all points in a graph can be divided into left and right parts, so that all edges in the graph are connected from the points in the left set to the points in the right set. There are no edges inside the left and right sets. The icon is as follows

This section talks about two parts, namely the coloring method and the Hungarian algorithm .

The coloring method is implemented by depth-first traversal, and the time complexity is O(n m); the time complexity of the Hungarian algorithm is theoretically O(n m), but the actual running time is generally much less than O(n m) .

An important property in graph theory: a graph is a bipartite graph, if and only if the graph does not contain odd rings

Odd-numbered ring refers to the odd number of edges in this ring. (The number of edges and the number of points in the ring are the same)

In a ring, suppose there are 4 points (even number) in total, because the bipartite graph requires that the points in the same set cannot be connected to each other.

Then point 1 belongs to set A, point 2 connected to point 1 should belong to set B, point 3 connected to point 2 should belong to set A, and point 4 connected to point 3 should belong to set B. Point 1 connected to point 4 should belong to set A. This can be dichotomy.

If the number of points in the ring is an odd number, it is assumed that point 1 belongs to set A at the beginning. After pushing around the ring, you will find that point 1 should belong to set B. This is a contradiction. So if there are odd rings, this graph must not be dichotomy.

You can use the coloring method to determine whether a graph is a bipartite graph. Use depth-first traversal to color each node in the graph from the root node. Each node is either black or white (2 types), as long as the coloring process If there is no contradiction, it means that the graph is a bipartite graph; otherwise, it is not a bipartite graph.

#### Dyeing method

Practice questions: acwing-860: Judging bipartite graphs by dyeing method

First wrong solution

```# include <iostream>
# include <cstring>
# include <algorithm>
using  namespace  std ;
const  int N = 1e5 + 10 , M = 2e5 + 10 ;
//Use adjacency table to store graph
int h[N], e[M ], ne[M], idx;

int n, m;
int color[N];

void  add ( int x, int y)  {
//The head insertion method of the linked list
e[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}

bool  dfs ( int x)  {
//Deep search all child nodes of this node
for ( int i = h[x]; i != -1 ; i = ne[i]) {
int u = e[i];//Child node
if (color[u] == -1 ) {
//If the child node has not been dyed, it is dyed directly and searched deeply
color[u] = !color[x];
if (!dfs(u)) return  false ;
} else  if (color[u] == color[x]) return  false ; //If the color of the child node and the parent node are the same, it means a contradiction
}
//After the deep search is over, there is no contradiction, then the dyeing is successful, and the judgment is the bipartite graph
return  true ;
}

int  main ()  {
memset (h, -1 , sizeof h);//Initialize an empty linked list
memset (color, -1 , sizeof color);//Initialize the color to -1, which means it has not been dyed
scanf ( "%d% d" , &n, &m);
while (m--) {
int x, y;
scanf ( "%d%d" , &x, &y);
add(x, y); //undirected graph, add two edges
}
color[ 1 ] = 0 ; //Color point 1 first.
//You can t directly dfs from one point, because the whole graph may not be a connected graph
//and other connected blocks are not necessarily bipartite graphs
//so to 1 ~ n all points sequentially stained
IF (the DFS ( 1 )) printf ( "Yes/the n-" );
the else  printf ( "No/the n-" );
return  0 ;
}
Copy code```

It is not possible to perform dfs directly from one point, because the entire graph may not be a connected graph. If you perform dfs from one point, you can only color the connected blocks where this point is located, and you cannot touch other connected blocks. The connected block of is not necessarily a bipartite graph, so all the points from 1 to n must be colored sequentially to ensure that all points are colored.

The correct solution is as follows

```# include <iostream>
# include <cstring>
# include <algorithm>
using  namespace  std ;
const  int N = 1e5 + 10 , M = 2e5 + 10 ; //Since it is an undirected graph, two edges need to be built, so the number of edges Set to 2 times
//Use the adjacency list to store the graph
int h[N], e[M], ne[M], idx; //Note the implementation of the singly linked list here, the array size is M

int n, m;
int color[N];

void  add ( int x, int y)  {
//The head insertion method of the linked list
e[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}

bool  dfs ( int x)  {
//Deep search all child nodes of this node
for ( int i = h[x]; i != -1 ; i = ne[i]) {
int u = e[i];//Child node
if (color[u] == -1 ) {
//If the child node has not been dyed, it is dyed directly and searched deeply
color[u] = !color[x];
if (!dfs(u)) return  false ;
} else  if (color[u] == color[x]) return  false ; //If the color of the child node and the parent node are the same, it means a contradiction, and the self-loop should also be a contradiction?
}
//After the deep search is over, there is no contradiction, then the dyeing is successful, and the judgment is the bipartite graph
return  true ;
}

int  main ()  {
memset (h, -1 , sizeof h);//Initialize an empty linked list
memset (color, -1 , sizeof color);//Initialize the color to -1, which means it has not been dyed
scanf ( "%d% d" , &n, &m);
while (m--) {
int x, y;
scanf ( "%d%d" , &x, &y);
}
bool flag = true ;
//Color all points in turn
for ( int i = 1 ; i <= n; i++) {
if (color[i] == -1 ) {
//The point is not yet colored, just go straight Coloring, just dye a color (0 or 1), and after dfs, dfs is completed, the connected block where this point is located is dyed
color[i] = 0 ;
//do dfs, if you are doing this If there is a contradiction in the coloring process of connected blocks, then directly break
if (!dfs(i)) {
flag = false ;
break ;
}
}
}
if (flag) printf ( "Yes\n" );
else  printf ( "No\n" );
return  0 ;
}
Copy code```

Problem solution: Java

```import java.util.*;

/**
* @Author yogurtzzz
* @Date 2021/6/30 16:42
**/
public  class  Main  {

static Scanner scanner = new Scanner(System.in);

static  int [] h, e, ne;
static  int idx;

static  int [] color;

public  static  void  main (String[] args)  {
int n = readInt(), m = readInt();
h = new  int [n + 1 ];
e = new  int [ 2 * m + 1 ];
ne = new  int [ 2 * m + 1 ];
color = new  int [n + 1 ];
Arrays.fill(h, -1 );

while (m--> 0 ) {
int a = readInt(), b = readInt();
}

boolean flag = true ;
//dyed
for ( int i = 1 ; i <= n; i++) {
if (color[i] == 0 ) {
//not yet dyed
color[i] = 1 ; //dyed
if (!dfs(i)) { //Deep search, after the end of the deep search, all points of the connected block where the point is located will be colored
flag = false ;
break ;
}
}
}
if (flag) System.out.println( "Yes" );
else System.out.println( "No" );
}

static  boolean  dfs ( int x)  {
for ( int i = h[x]; i !=- 1 ; i = ne[i]) {
int u = e[i];
if (color[u] == 0 ) {
//Not yet dyed, dye directly
color[u] = 3 -color[x];
//Deep search after dyeing
if (!dfs(u)) return  false ;
} else  if (color[u] == color[x]) return  false ;
}
return  true ;
}

static  void  add ( int a, int b)  {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}

static String readString ()  {
return scanner.next();
}

static  int  readInt ()  {
return scanner.nextInt();
}
}
Copy code```

Homework Questions: acwing-257: Detaining Criminals

You can use bipartite graphs to do it, or you can use union search

```//TODO
copy code```

#### Hungary algorithm

The Hungarian algorithm is used to find the maximum matching of the bipartite graph given a bipartite graph.

Given a bipartite graph G, in a subgraph M of G, any two edges in the edge set of M are not attached to the same vertex, then M is said to be a match . That is, each point is connected by only one edge, and there is no point, and multiple edges are connected at the same time. (Refer to the example of yxc: boys and girls are in love pairing, how many pairs can you make together)

The group of matches with the largest number of edges among all matches is called the maximum match of the bipartite graph. The number of edges is the maximum number of matches. Assuming a bipartite graph, some nodes on the left half represent boys, and some nodes on the right half represent girls. A boy node and a girl node are connected by an edge, which means that the two people have an emotional basis and can develop into a couple. When we put a pair of men and women into a pair, it is called the two nodes match. The core idea of the Hungarian algorithm is : we enumerate all boys (nodes) on the left half, and each time we try to find an object for the current boy. Let's first find all the girls that this guy likes. (That is, find all the nodes on the right side connected by this node). Traverse these girls, when a girl is not paired with other boys, directly match this girl with this boy. Then the boy is paired successfully. When the girl has been paired with other boys, try to find a spare tire for the girl s boyfriend. If this girl s boyfriend has other alternative spare tires. Then pair the girl's boyfriend with her spare tire. Then pair this girl with the current boy. Look for it like this...

Practice questions: acwing-861: the largest matching of bipartite graphs

```# include <iostream>
# include <cstring>
# include <algorithm>
using  namespace  std ;
const  int N = 1010 , M = 1e5 + 10 ;

int h[N], e[M], ne[M], idx;
int match[N];
bool st[N]; //state variables

int n1, n2, m;

void  add ( int a, int b)  {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}

//Find a girlfriend for a boy
bool  find ( int x)  {
//Find all the girls that the boy likes
for ( int i = h[x]; i != -1 ; i = ne[i]) {
int u = e[i]; //The girl s node number
if (st[u]) continue ; //If the girl has been marked, skip
st[u] = true ; //First mark the girl so that Skip this girl in subsequent recursion
if (match[u] == 0 || find(match[u])) {
//If the current girl is not matched, or can find another backup for the boy who has been matched by this girl Tire, you can
match[u] = x;
return  true ;
}
}
return  false ; //I still can't find a circle
}

int  main ()  {
memset (h, -1 , sizeof h);
scanf ( "%d%d%d" , &n1, &n2, &m);
while (m--) {
int a, b;
scanf ( "% d%d" , &a, &b);
add(a, b); //only connect from the left half to the right half
}

//enumerate all points on the left half
int res = 0 ;
for ( int i = 1 ; i <= n1; i++) {
//every time a boy finds a girlfriend, clear the state variable
memset (st, false , sizeof st);
if (find(i)) res++;
}
printf ( "%d\n" , res);
return  0 ;
}
Copy code```

After-school questions: acwing-372: Chess and cards placement

```//TODO
copy code```

summary

There are two main algorithms related to bipartite graphs

• Coloring method: is used to judge whether a graph is a bipartite graph
• Hungarian algorithm: it is used to find the maximum matching of the bipartite graph