## 【算法笔记】基于线性代数的一般图匹配算法

##### ★,°:.☆(￣▽￣)/\$:.°★ 。
maximum_matchings_via_gaussian_keynote

## 【Timus 1099】Work Scheduling

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1000000;

int n,match[MAXN],fa[MAXN],que[MAXN],fro,bak;
int next[MAXN],mark[MAXN],vis[MAXN];

inline int find(int w){
int f = fa[w], tmp;
while (f != fa[f]) f = fa[f];
while (w != f) tmp=fa[w], fa[w]=f, w=tmp;
return f;
}

inline void merge(int a, int b){
int f1 = find(a), f2 = find(b);
if (f1 != f2) fa[f1] = f2;
}

inline int LCA(int x, int y){
static int t = 0; t++;
while (true){
if (x) {
x = find(x);
if (vis[x] == t) return x;
else {
vis[x] = t;
x = next[match[x]];
}
} swap(x, y);
}
}

inline void gather(int a, int p){
while (a != p){
int b = match[a], c = next[b];
if (find(c) != p) next = b;
if (mark[b] == 2) mark[que[++fro]=b] = 1;
if (mark == 2) mark[que[++fro]=c] = 1;
merge(a, b); merge(b, c);
a = c;
}
}

inline void Augment(int s){
for (int i=1;i<=n;i++) next[i]=mark[i]=vis[i]=0, fa[i]=i;
mark[s] = 1; que[fro=bak=1] = s;
while (bak <= fro) {
int w = que[bak++];
if (match[w] == to[i]) continue;
else if (find(to[i]) == find(w)) continue;
else if (mark[to[i]] == 2) continue;
else if (mark[to[i]] == 1) {
int lca = LCA(w, to[i]);
if (find(w) != lca) next[w] = to[i];
if (find(to[i]) != lca) next[to[i]] = w;
gather(w, lca);
gather(to[i], lca);
} else if (!match[to[i]]) {
next[to[i]] = w;
for (int u=to[i]; u; ) {
int v = next[u];
int fv = match[v];
match[v] = u; match[u] = v;
u = fv;
}
return;
} else {
next[to[i]] = w;
mark[que[++fro] = match[to[i]]] = 1;
mark[to[i]] = 2;
}
}
}
}

inline void AddEdge(int a, int b){
}

int main(){
scanf("%d",&n); int a,b;