Minimum spanning tree and bipartite graph in graph theory (acwing template)

Directory navigation ：

Minimum spanning tree ：

For one there is n A picture of a point , Edge must be greater than or equal to n − 1 The article , Minimum spanning tree , Is to choose from these edges

n -1 Bar out to connect all n A little bit , And this n − 1 The sum of the edge weights of the edges is the smallest of all schemes

Say a little more ：

It's in the original picture n A little bit , Edge greater than n-1 strip , Delete the redundant edges , Make the rest n-1 The side length of the strip is the smallest

 Prim The algorithm constructs the minimum spanning tree

The diagram written by the great God is very vivid ：

Minimum spanning tree _ZhuRanCheng The blog of -CSDN Blog _ Minimum spanning tree

  To sum up, it is ： Greedy Algorithm

Choose the smallest edge every time , And put the smallest edge into the set I have updated , And use this set to update other points

  Algorithmic thought ：

inf=0x3f3f3f3f// A large number 
dist[i]<----inf// The initialization distance is a large number 
for(i=0;i<n;i++)
{
	t<---- Find the point closest to the set outside the set 
	 use t Update the distance from other points to the collection 
	st[t]=true// Mark 
}

Example ：

Given a n A little bit m Undirected graph of strip and edge , There may be double edges and self rings in the graph , The edge weight may be negative .

Find the sum of tree edge weights of the minimum spanning tree , If the minimum spanning tree does not exist, output impossible.

Given an undirected graph with weights G=(V, E), among V Represents the set of points in the graph ,E Represents a set of edges in a graph ,

n=|V|,m=|E|.

from V All of n A vertex and E in n-1 An undirected connected subgraph composed of edges is called G A spanning tree of , The spanning tree in which the sum of the weights of the edges is the smallest is called an undirected graph G The minimum spanning tree of

  The meaning of the title is the meaning summarized above , If there is no connection between two points , Then the minimum spanning tree cannot be generated

Code implementation ：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N], dist[N];// A dense picture 
// Adjacency matrix stores all edges 
//dist Store other points to S Distance of ;
bool st[N];// Judge array 

int prim() {
    // If the graph is disconnected, return INF,  Otherwise return to res
    memset(dist, INF, sizeof dist);// The initialization distance is a large number 
    int res = 0;// result 

    for (int i = 0; i < n; i++) 
    {
        int t = -1;// Any meaningless number is enough 
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        // Look for a set of outliers S Some recent       
        if (i && dist[t] == INF) return INF;// The first time i=0  Do not execute the if
        // Judge whether it is connected , Is there a minimum spanning tree 

        if (i) res += dist[t];// If i>0  And t To the assembly S The distance to dist[t]
        //cout << i << ' ' << res << endl;
        st[t] = true;// Mark 
        // Update the latest S Weight sum of 
        for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);// And dijstra Where the algorithm is different ：
    }

    return res;
}

int main() {
    cin >> n >> m;// points , Number of edges 
    int u, v, w;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j) g[i][j] = 0;// Heavy edge ： The distance to oneself is initialized to 0
            else g[i][j] = INF;// Not for re editing ：i->j The distance is initialized to INF

    while (m--)//m side 
    {
        cin >> u >> v >> w;//u->v The length of w
        g[u][v] = g[v][u] = min(g[u][v], w);// Put the original INF The side length of 
    }
    int t = prim();// Receive return value 
    // Temporary storage prevents the function from executing twice, resulting in only returning 0
    if (t == INF) puts("impossible");// Description: unable to connect 
    else cout << t << endl;// Sum of output side lengths 
}

  And dijstra The difference and connection of algorithms ：

You can see the whole and dijstra The idea of the algorithm is the same , The code is about the same

The difference is ：Dijkstra The algorithm is to update the distance to the starting point ,Prim Is to update to the collection S Distance of

In the code is reflected as ：for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);

and dijstra Algorithm for ：

for (int j = 1; j <= n; j++)// Traverse 1 It's on the n Number point
            dist[j] = min(dist[j], dist[t] + g[t][j]);//1~j The distance between points becomes ：1~t Distance of +t~j Distance of

---

Kruskal Algorithm

Illustrations of algorithms are still recommended ：

Minimum spanning tree _ZhuRanCheng The blog of -CSDN Blog _ Minimum spanning tree

  Generalization ： Or greedy ！

Sort each edge by its length , The side length is small on the top ！ Then we get the shortest distance from an edge to an edge , Connect in order , That is to say, connect it first , In the process of edge construction , Loops may occur ：1->2->3->1, This is not allowed , So skip this side and don't choose , Finally, a minimum spanning tree without loops is formed ！

  Realization function ：

（1） Sort , Sort by side length

（2） a key ： Judge whether adding this edge will form a loop

You can think of the connected blocks in the data structure section , Just prove that the ancestors of these two sides are the same , Then come to Unicom

（3） Add this edge res, Finally back to res that will do

Code brief ：

 Algorithm ideas ：① Sort all edges by weight from small to large 
② Enumerate each edge  a,b, The weight is c

if a,b Disconnected  

​	 Add this edge to the set 

Example ：

Given a n A little bit m Undirected graph of strip and edge , There may be double edges and self rings in the graph , The edge weight may be negative .

Find the sum of tree edge weights of the minimum spanning tree , If the minimum spanning tree does not exist, output impossible.

Given an undirected graph with weights G=(V, E), among V Represents the set of points in the graph ,E Represents a set of edges in a graph ,n=|V|,m=|E|.

from V All of n A vertex and E in n-1 An undirected connected subgraph composed of edges is called G A spanning tree of , The spanning tree in which the sum of the weights of the edges is the smallest is called an undirected graph G The minimum spanning tree of .

  Code implementation ：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 5;
int n, m;
struct Edge // Defining structure , Convenient for correspondence , And sort 
{
	int u, v, w;
	bool operator<(const Edge& a) const // Preprocessing of sorting 
	{
		return w < a.w;
	}
}edge[N];
int p[N];
int find(int x)// And look for the same ancestors in the search set 
{
	return p[x] == x ? x : p[x] = find(p[x]);
}
int main() 
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) 
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		edge[i] = { u,v,w };
	}
	sort(edge, edge + m);// Yes m Sort by edge 
	for (int i = 1; i <= n; i++) p[i] = i;// Storage nodes 
	int cnt = 0, sum = 0;//cnt： frequency   sum： The sum of side lengths 
	for (int i = 0; i < m; i++)// I'm going to go through each edge 
	{
		int a = edge[i].u, b = edge[i].v, w = edge[i].w;
		a = find(a);// seek a The ancestor node of 
		b = find(b);// seek b The ancestor node of 
		if (a != b)// If the ancestral node is different ： prove a,b Unconnected 
		{
			cnt++;// take a,b connected , frequency ++
			sum += w;// Add the side length sum The sum of the 
			p[a] = b;// take a Nodes connecting to b node 
		}
	}
	if (cnt < n - 1) puts("impossible");
	else printf("%d", sum);
}

The core ：

Understand that the ancestor nodes before connection are different , After connection, it is the same , If it is 1->2->3  3->1  ： We can't connect , Why? ？ Because their ancestral nodes are the same , So skip this situation , This perfectly realizes the Kruskal Algorithm

---

Bipartite graph

Important conclusions ： A graph is a bipartite graph , If and only if the graph does not contain odd rings

（1） To judge a bipartite graph by coloring

problem ：

Given a n A little bit m Undirected graph of strip and edge , There may be double edges and self rings in the graph .

Please judge whether this graph is bipartite

  The illustration ：

Bipartite graph algorithm summary ( Dyeing method 、 hungarian algorithm )_wmy0217_ The blog of -CSDN Blog _ Coloring algorithm

  summary ： Dye the starting point as 1, The tinge connected with the starting point is 2, By analogy , The colors of adjacent dots cannot be the same , If there is no conflict , Then the graph is a bipartite graph , If there is a conflict , Then the graph is not a bipartite graph

Depth first search ：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx; // Storage of adjacency table 
int color[N];

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

bool dfs(int u, int c)
{
	color[u] = c; // At this point u The color of is  c 

	for (int i = h[u]; i != -1; i = ne[i])// Traversal of the list 
	{
		int j = e[i];// Record nodes 
		if (!color[j]) //u  The adjacency point  j  Not stained   
		{
			dfs(j, 3 - c); // u If the color of is 1,j Namely 3-1=2;u If the color of is 2,j Namely 3-2=1 
		}
		else if (color[j] == c) return false; // Two adjacent dots are dyed in the same color 
	}
	return true;
}

int main()
{
	cin >> n >> m;
	memset(h, -1, sizeof(h));

	while (m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a); //  An undirected graph has two opposite sides  
	}

	bool flag = true;
	for (int i = 1; i <= n; i++) // Traverse all points of the graph  
		if (!color[i])// Unstained 
		{
			if (!dfs(i, 1))// take 1 Node No. is colored 1, And dye it downward  ： If dfs The result is false, Then mark flag=false
			{
				flag = false;
				break;
			}
		}

	if (flag)  cout << "Yes";
	else cout << "No";
}

Breadth first search ：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII; //first Storage point No ,second Save color  
const int N = 1e5 + 10, M = 2e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx; // Storage of adjacency table 
int color[N];

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

bool bfs(int u)
{
	queue<PII> q;
	q.push({ u,1 });// The team 
	color[u] = 1; // At this point u The color of is  c 

	while (q.size()) // The queue is not empty 
	{
		PII t = q.front();
		q.pop();// Take out the team leader 

		int ver = t.first, c = t.second;
		for (int i = h[ver]; i != -1; i = ne[i])// Traversing the linked list 
		{
			int j = e[i];

			if (!color[j]) // Not stained 
			{
				color[j] = 3 - c;
				q.push({ j,3 - c });// The team 
			}
			else if (color[j] == c) return false; // Two adjacent dots are dyed in the same color  
		}
	}
	return true;
}

int main()// And dfs Same framework 
{
	cin >> n >> m;
	memset(h, -1, sizeof(h));

	while (m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a); //  An undirected graph has two opposite sides  
	}

	bool flag = true;
	for (int i = 1; i <= n; i++) // Traverse all points of the graph  
		if (!color[i])
		{
			if (!bfs(i))
			{
				flag = false;
				break;
			}
		}

	if (flag)  cout << "Yes";
	else cout << "No";
}

Fallible ：

The storage of single linked lists does not have to be connected in order, such as ：

A tree structure ：

  The structure stored in the single linked list ：

  And dfs The difference lies in the connection order of the single linked list , The point is to build the simulation in your mind dfs,bfs

---

hungarian algorithm

Algorithm ideas ：

Specific examples ： Brother, I like that girl , Why don't you change to another girl who likes you , This girl let me

Bipartite graph algorithm summary ( Dyeing method 、 hungarian algorithm )_wmy0217_ The blog of -CSDN Blog _ Coloring algorithm

 

 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510, M = 1e5 + 10;
int n1, n2, m;
int h[N], e[M], ne[M], idx; // Adjacency list 
int match[N];
bool st[N];

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

bool find(int x)
{
	for (int i = h[x]; i != -1; i = ne[i]) //  Traverse  x  Boys like all girls  
	{
		int j = e[i];
		if (!st[j]) //  If st[j] = true  Don't think about this girl  
		{
			st[j] = true; //  Mark  j  This girl , The function is if this girl has a boyfriend , When we went to see if her boyfriend could be with other girls , There is no need to consider his current object  j  了  
			if (match[j] == 0 || find(match[j]))//  The girl has no partner or her boyfriend can be with other girls she likes  
			{
				match[j] = x; // The match is successful  
				return true;
			}
		}
	}
	return false;
}

int main()
{
	cin >> n1 >> n2 >> m;
	memset(h, -1, sizeof(h));
	while (m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b); // It's enough to save only one male to female side  
	}
	int res = 0; //  Current matching quantity 
	for (int i = 1; i <= n1; i++) //  Traverse every boy 
	{
		memset(st, false, sizeof(st)); // On behalf of the girl has not considered , Every girl only considers once 
		if (find(i)) res++;  //  The boy matched  
	}
	cout << res;
}

---