二分图、拓扑与欧拉

1、二分图匹配问题（判断是否二分图可以使用并查集）
`// 邻接表存储图
int n1, n2, m;
int h[500], e[100010],ne[100010], idx = 0;
//st 标记是否递归找过， match[x]：和 x 编号的男生的编号
int st[510], match[510];
//存图函数
void add(int a, int 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]){
int b = e[i];
if(!st[b]){//打标记
st[b] = 1;
// 当前尝试点没有被匹配或者和当前尝试点匹配的那个点可以换另一个匹配
if(match[b] == 0 || find(match[b])){
// 和当前尝试点匹配在一起
match[b] = x;
return true;
}
}
}
return false;
}

int main(){
memset(h, -1, sizeof h);
cin >> n1 >> n2 >> m;
// 保存图，因为只从一遍找另一边，所以该无向图只需要存储一个方向
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
add(a, b);
}
int res = 0;
//为各个点找匹配
for(int i = 1; i <= n1; i++){
memset(st, 0, sizeof st);
//找到匹配
if(find(i)) res++;
}
cout << res;
return 0;
}`

2、拓扑排序（核心在出度和入度，相当于bfs思路，常用于有多重先后顺序的点排列）（下面的例题用于求取所有起点出发到所有终点的总路径，拓扑在此并非用于‘求’排列，而是‘维护’题意的排列并求路径）
`const int MOD = 80112002;
int n, m; // n: 节点数, m: 边数
int rudu[5010];int chudu[5010];// 每个点的出度入度
int sg[5010]; // 标记数组，记录是否已入队
int dp[5010]; // dp[i]: 从任意起点到达i的路径数
int ans = 0;

// cb[x]: 从x出发的所有“反向边”目标（即图的反向边存储）
// rb[x]: 正向边的邻接表（可选）
unordered_map<int, vector> cb;
unordered_map<int, vector> rb;

void tppx() {
queue q;
for (int i = 1; i <= n; i++) {
if (rudu[i] == 0) {
q.push(i);// 初始化：所有入度为0的点是起点
dp[i] = 1;// 起点到自身路径数 = 1
sg[i] = 1;
}
}

// BFS式拓扑排序
while (!q.empty()) {int up = q.front(); q.pop();// 遍历up的所有后继节点（反向存储时要注意方向）for (int i = 0; i < cb[up].size(); i++) {int v = cb[up][i];rudu[v]--;  // 消去一条入度// 动态规划转移：dp[v] += dp[up]dp[v] = (dp[v] + dp[up]) % MOD;}for (int i = 1; i <= n; i++) {if (rudu[i] == 0 && !sg[i]) {q.push(i);sg[i] = 1;// 入度归0的点入队}}
}//如果要判断可否拓扑排序，这里可以加一个if，判断是否所有点sg都记录为已经入队过

}

int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int A, B; cin >> A >> B;
// 注意这里边是 B -> A （存反向图） 因为作者的dp计算方向是反向的
rudu[A]++; // A 的入度 +1
cb[B].push_back(A); // 记录反向边 B -> A
rb[A].push_back(B); // 记录正向边 A -> B
chudu[B]++; // B 的出度 +1
}

tppx();
for (int i = 1; i <= n; i++) {if (chudu[i] == 0) {ans = (ans + dp[i]) % MOD;// 所有出度为0的节点都是“终点”，记录到它们的所有路径}
}cout << ans << endl;
return 0;

}`