Description

有一个$n$个点的无向图,其中只有$m$对点之间没有连边,保证这张图可以被分为至多两个团.

对于$m$对未连边的点对,判断有哪些点对满足将他们连边后最大团的大小增加.

Input

第一行包含两个正整数$n$ , $m$ 。

接下来$m$行描述$m$个没有连边的点对.

$n \le 10^4, m \le 1.5 \times 10^5$,没有重边自环.

Output

第一行一个整数表示合法点对数。

接下来若干行每行两个整数表示一个无序点对(编号小的在前),按字典序大小排序.

Solution

其实是经典问题,然而还是不会做.

考虑将原图取反,也就是输入的$m$条边构成的图.这个图一定是个二分图,因为题目保证了原图可以被至多两个团覆盖.

原图上的最大团,也就是反图上的最大独立集,而二分图的最大独立集等于点数减去最大匹配数.那么题目就是问去掉哪些边后最大匹配数减少,也就是哪些边一定在最大匹配上.

这题中$n, m$较大,需要用Dinic算二分匹配.怎么判断哪些边一定在最大匹配上?显然它们一定要满流,其次边上的两个点在残量网络上不能在同一个强连通分量中,因为如果他们在同一个环中,就可以将环上未匹配的边设为匹配边,匹配边设为未匹配边,最大匹配不变.

$O(m \sqrt{n})$

Source

#include <bits/stdc++.h>

#define pb push_back
#define For(i, j, k) for (int i = j; i <= k; i++)

using namespace std;

const int N = 1e4 + 10, M = 3e5 + 10;

struct Edge {
	int u, v;

	Edge (int x, int y) {
		u = x, v = y;
		if (u > v) swap(u, v);
	}

	bool operator < (const Edge& B) const {
		return u ^ B.u ? u < B.u : v < B.v;
	}
};

vector<Edge> ans;
vector<int> G[N];
int n, m;

struct Dinic {

	int Begin[N], Next[M], to[M], flow[M], e;

	Dinic() { e = 1; }

	void add(int u, int v, int f) {
		to[++e] = v, Next[e] = Begin[u], Begin[u] = e, flow[e] = f;
		to[++e] = u, Next[e] = Begin[v], Begin[v] = e, flow[e] = 0;
	}

	int dis[N];
	int S, T;

	bool BFS() {
		queue<int> q;
		memset(dis, 0, sizeof dis);
		q.push(S), dis[S] = 1;
		while (!q.empty()) {
			int o = q.front(); q.pop();
			for (int i = Begin[o]; i; i = Next[i]) {
				int u = to[i];
				if (flow[i] && !dis[u]) dis[u] = dis[o] + 1, q.push(u);
			}
		}
		return dis[T];
	}

	int cur[N];

	int DFS(int o, int maxf) {
		if (!maxf || o == T) return maxf;
		int sumf = 0, f;
		for (int &i = cur[o]; i; i = Next[i]) {
			int u = to[i];
			if (dis[u] == dis[o] + 1 && (f = DFS(u, min(flow[i], maxf)))) {
				maxf -= f, sumf += f;
				flow[i] -= f, flow[i ^ 1] += f;
			}
		}
		return sumf;
	}

	int dfn[N], low[N], bel[N], st[N];
	int p, c, clk;

	void Tarjan(int o) {
		low[o] = dfn[o] = ++clk;
		st[++p] = o;
		for (int i = Begin[o]; i; i = Next[i]) if (flow[i]) {
			int u = to[i];
			if (!dfn[u]) {
				Tarjan(u);
				low[o] = min(low[o], low[u]);
			} else if (!bel[u]) {
				low[o] = min(low[o], dfn[u]);
			}
		}
		if (dfn[o] == low[o]) {
			bel[o] = ++c;
			while (st[p] != o) bel[st[p--]] = c;
			--p;
		}
	}

	void work(int s, int t) {
		S = s, T = t;
		int ret = 0;
		while (BFS()) {
			For(i, 1, T) cur[i] = Begin[i];
			ret += DFS(S, n);
		}
		For(i, 1, T) if (!dfn[i]) 
			Tarjan(i);
		For(i, 1, n) for (int j = Begin[i]; j; j = Next[j]) {
			int u = to[j];
			if (u <= n && bel[u] != bel[i] && !flow[j] && j % 2 == 0) 
				ans.pb(Edge(u, i));
		}
	}

}F;

int col[N];

void DFS(int o) {
	for (int u : G[o]) {
		if (!col[u]) {
			col[u] = 3 - col[o];
			DFS(u);
		}
		if (col[o] == 1) F.add(o, u, 1);
	}
	if (col[o] == 1) F.add(n + 1, o, 1);
	else F.add(o, n + 2, 1);
}

int main() {

	scanf("%d%d", &n, &m);
	For(i, 1, m) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].pb(v), G[v].pb(u);
	}
	For(i, 1, n) if (!col[i]) col[i] = 1, DFS(i);
	For(i, 1, n) G[i].clear();
	F.work(n + 1, n + 2);

	sort(ans.begin(), ans.end());
	printf("%lu\n", ans.size());
	for (Edge s : ans) printf("%d %d\n", s.u, s.v);

	return 0;
}