This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

Reference blogs: Chained Forward Star — The Most Easy-to-Understand Explanation, Algorithm Explanation: Bipartite Matching [Graph Theory], Fun Algorithm Series — Hungarian Algorithm, Hungarian Algorithm and Augmenting Paths

Did this during summer but forgot to post it, lol.

---

@[TOC](Table of Contents)

---

I. Chained Forward Star

1. What Is It

If adjacency lists are hard to write but efficient, and adjacency matrices are easy to write but inefficient, then forward stars are a relatively middle-ground data structure. Forward stars are easy to write but not very efficient. However, after optimization into chained forward stars, efficiency is significantly improved. Although chained forward stars are not widely used worldwide, they are an excellent data structure when you don’t want to write complex adjacency lists.

-- From Baidu Encyclopedia

Chained forward star is essentially a statically built adjacency list, a special edge set array with time complexity O(m) and space complexity O(m). Traversal complexity is also O(m), and it can conveniently find all adjacent edges for every node.

2. How to Store the Graph

We need the following arrays:

1. head[i] array: represents the index of the first edge starting from vertex i, generally initialized to -1, indicating no edges start from this vertex.
2. edge[i] struct array: where edge[i].to represents the endpoint of the i-th edge, edge[i].Next represents the storage position of the next edge with the same starting point as the i-th edge, and edge[i].w is the edge weight.

Definition and Initialization

const int maxn = 10000;//最大顶点数
int N,M,mcnt;//顶点数、边数
int head[maxn];//以i为起点的第一条边在edge数组的下标
struct Edge {
    int to, w, Next;//终点、边权、同起点的下一条边的编号
} edge[maxn];
void init() {
    memset(head, -1, sizeof(head));
    mcnt = 0;
}

Adding Edges

void add_edge(int u, int v, int w) {
    edge[mcnt].to = v;
    edge[mcnt].w = w;
    edge[mcnt].Next = head[u];//将下一条边的编号赋给Next
    head[u] = mcnt++;//更新head数组
}

Traversal

for(int i = 1; i <= N; ++i) {
    for(int j = head[i]; j != -1; j = edge[j].Next) {   //遍历以i为起点的边
        //其他操作
    }
}

II. Bipartite Matching

1. Bipartite Graph

Baidu Encyclopedia explains it as follows:

A bipartite graph, also known as a bigraph, is a special model in graph theory. Let G=(V,E) be an undirected graph. If the vertex set V can be partitioned into two disjoint subsets (A,B), and every edge (i,j) in the graph connects a vertex i in A to a vertex j in B, then graph G is called a bipartite graph.

Simply put, a graph is divided into two parts, and edges only exist between vertices in different parts — no edges exist between vertices in the same part.

2. Matching

• Given a bipartite graph G, in a subgraph M of G, if any two edges in M’s edge set {E} do not share a common vertex, then M is called a matching.
• Maximal Matching: Under the current matching, no more unmatched edges can be added to increase the number of matched edges.
• Maximum Matching: The matching with the most edges among all maximal matchings. Finding such a maximum-edge subset is called the maximum matching problem.
• If every vertex in a matching is associated with some edge in the graph, the matching is called a perfect matching, also known as a complete matching.
• If P is a path in graph G connecting two unmatched vertices, and edges belonging to M and edges not belonging to M alternate on P, then P is called an augmenting path relative to M.

3. Hungarian Algorithm

The Hungarian algorithm can be used in all bipartite matching problems except bipartite multi-matching. It is essentially the core algorithm for bipartite matching, based on network flow thinking, with its core being finding augmenting paths. The specific operation is basically… matchmaking. For the detailed idea, see this blog: Fun Algorithm Series — Hungarian Algorithm Here’s a summary: If there’s a chance, go for it. If there’s no chance, create one and still go for it.

Core Code

Recursively find matches:

bool find(int x){
 int i,j;
 for (j=1;j<=m;j++){    //扫描每个妹子
  if (line[x][j]==true && used[j]==false)
  //如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题，但是没有成功，所以就不用瞎费工夫了）
  {
   used[j]=1;
   if (girl[j]==-1 || find(girl[j])) {
    //名花无主或者能腾出个位置来，这里使用递归
    girl[j]=x;
    return true;
   }
  }
 }
 return false;
}

In the main program, scan each person, note the used array reset:

for (i=1;i<=n;i++)
{
 memset(used,0,sizeof(used));    //这个在每一步中清空
 if find(i) all+=1;
}

Example Problems

A - Fire Net

Problem Summary and Approach

Summary: An N*N city map where ”.” represents a position where a small castle can be placed to shoot in four directions, and “X” represents a wall that blocks shooting. Place as many small castles as possible in the city so that no two castles can destroy each other. A configuration is legal if and only if no two castles are on the same horizontal row or vertical column unless separated by at least one wall. Approach: First traverse each row — segments separated by walls count as different columns, forming region X of the bipartite graph. Then traverse each column — segments separated by walls count as different rows, forming region Y. edge[i][j] indicates whether point i in region X and point j in region Y are connected. Find the maximum matching of this bipartite graph (castles are placed at row-column intersections, which are unique). This problem is obviously simpler with an adjacency matrix for the transformed graph…

Code

Note that the col array must be initialized to -1.

// A - Fire Net
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 1005;
const int inf  = 0x3f3f3f;
int N,M,rcnt,ccnt,ans;
string str;
struct Vertex {
    char flag;
    int r, c;//该点位于的真实行列
}map[maxn][maxn],now;
int edge[maxn][maxn];
int col[maxn];
bool used[maxn];
void init() {
    rcnt = ccnt = ans = 0;
    memset(used, 0, sizeof(used));
    memset(col, -1, sizeof(col));
    memset(edge, 0, sizeof(edge));
}
bool find_x(int x) {
    for(int j = 0; j < ccnt; ++j) {
        if(edge[x][j] == 1 && !used[j]) {
            used[j] = true;
            if(col[j] == -1 || find_x(col[j])) {
                col[j] = x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin >> N && N) {
        init();
        for(int i = 0; i < N; ++i) {
            cin >> str;
            for(int j = 0; j < N; ++j) {
                map[i][j].flag = str[j];
            }
        }
        for(int j = 0; j < N; ++j, ++ccnt) {//每列
            for(int i = 0; i < N; ++i) {
                if(map[i][j].flag == 'X' && i+1 < N && map[i+1][j].flag != 'X')
                    ++ccnt;//每一列中不联通的视为不同列
                map[i][j].c = ccnt;
            }
        }
        for(int i = 0; i < N; ++i, ++rcnt) {//每行
            for(int j = 0; j < N; ++j) {
                if(map[i][j].flag == 'X' && j+1 < N && map[i][j+1].flag != 'X')
                    ++rcnt;//每一行中不联通的视为不同行
                map[i][j].r = rcnt;
            }
        }
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < N; ++j) {
                if(map[i][j].flag == '.') {
                    now = map[i][j];
                    edge[now.r][now.c] = 1;
                }
            }
        }
        for(int i = 0; i < rcnt; ++i) {
            memset(used, 0, sizeof(used));
            if(find_x(i)) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

B - The Accomodation of Students

Problem Summary and Approach

Summary: Given n students and m pairs of students who know each other, divide the students into two groups so that no two students in the same group know each other. If this is achievable, arrange them into double rooms. Remember, only pairs from the previously given set can share a room, meaning only known students can live together. Calculate the maximum number of pairs that can be arranged into double rooms. Approach: Bipartite graph verification and matching. Bipartite verification uses the coloring method, and matching uses the Hungarian algorithm.