Category: Union Find Set

题目传送门：http://acm.timus.ru/problem.aspx?space=1&num=1099
离线版题目：http://paste.ubuntu.com/19164744/

一般图匹配的板题
然而抄范大神的代码抄错了，调了一个下午QAQ
详细情况见之后的博文吧，会单独写一篇算法笔记的

#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];
int T,nxt[MAXN],head[MAXN],to[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++];
		for (int i=head[w];i;i=nxt[i]){
			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){
	to[++T] = b; nxt[T] = head[a]; head[a] = T;
	to[++T] = a; nxt[T] = head[b]; head[b] = T;
}

int main(){
	scanf("%d",&n); int a,b;
	while (~scanf("%d%d",&a,&b)) AddEdge(a, b);
	for (int i=1;i<=n;i++) if (!match[i]) Augment(i);
	
	int vout = 0;
	for (int i=1;i<=n;i++) if (match[i]) vout++;
	printf("%d\n",vout);
	for (int i=1;i<=n;i++) if (match[i] > i) printf("%d %d\n",i,match[i]);
	return 0;
}

另外，此题有坑QAQ
边数巨多，TM还不告诉你是RE，给你说的是TLEQAQ

题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/06/water_meeting.pdf

一看这题，TM这不今年wc的T1吗？哎呀，还是不会带花树QAQ，哎呀冬令营的时候网络流搞了40分，那就来写网络流吧！
于是开始骚写网络流。 然后写完了发现过不了样例QAQ 然后想了几分钟突然发现：
如果只考虑奇偶的话，这个一个联通块里不最多只有一个半空的筐QAQ
于是最后写了一个并查集。 后来问一问，发现带花树也是可以的，但是只有80分（╯－＿－）╯╧╧

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}	

const int MAXN = 400000;
const int INF = 100000000;

int n,m,A[MAXN],B[MAXN],bot[MAXN];
int vout,fa[MAXN],sum[MAXN],str[MAXN];
int Q[MAXN],cnt;

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 connect(int b, int a){
	int f1=find(a),f2=find(b);
	if (f1 != f2) fa[f1] = f2;
}

int main(){
	freopen("cpn.in","r",stdin);
	freopen("cpn.out","w",stdout);
	n = read(); m = read();
	for (int i=1;i<=m;i++) fa[i] = i;
	for (int i=1;i<=n;i++){ 
		A[i] = read(); B[i] = read();
		bot[A[i]]++; connect(A[i],B[i]);
	}	
	for (int i=1;i<=m;i++) find(i);
	for (int i=1;i<=m;i++) if (bot[i]%2)
		{sum[fa[i]]++; str[fa[i]] = i;}
	for (int i=1;i<=m;i++) if (sum[i]%2)
		{vout++; Q[++cnt]=str[i];}
	 
	printf("%d\n",vout);
	for (int i=1;i<=cnt;i++)
		printf("%d\n",Q[i]);
	
	return 0;
}