给定一个可以划分为不超过两个团的稠密图，以补图的形式描述。求有多少对点满足在它们之间建边后最大团的大小会增加。(n leq 10^4, m leq 1.5 imes 10^5)
Solution
原图的最大团就是补图的最大独立集，由题意补图是二分图，于是转化为求删去哪些边可以使得二分图的最大独立集减少
考虑到最大独立集数=最大匹配数，于是转化为求哪些边一定在最大匹配里
定理 二分图的某条边一定在最大匹配中当且仅当这条边满流，且残量网络中这条边的两个顶点不在同一个 SCC 中
于是我们跑出一个最大匹配，并残量网络并跑 Tarjan，枚举每条匹配边看 SCC 是否相同即可
注意这里用匈牙利会 T，所以要跑最大流
由于数据输入时我们不知道哪个点在哪个部，所以要先二分图染色一下
发现我的强联通板子是假的……
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
namespace scc {
vector <int> g[N],scc[N];
int ind,f[N],siz[N],dfn[N],low[N],vis[N],s[N],bel[N],top,tot,n,m,d[N];
char ch[N];
void make(int p,int q) {
d[q]++;
g[p].push_back(q);
}
void dfs(int p) {
s[++top]=p;
dfn[p]=low[p]=++ind;
for(int i=0;i<g[p].size();i++) {
int q=g[p][i];
if(!dfn[q]) dfs(q), low[p]=min(low[p],low[q]);
else if(!bel[q]) low[p]=min(low[p],dfn[q]);
}
if(dfn[p]==low[p]) {
++tot;
for(int i=0;i!=p;) {
i=s[top--];
bel[i]=tot;
scc[tot].push_back(i);
}
}
}
void solve(int _n) {
n=_n;
for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
}
}
namespace flow {
const int maxn = 500005;
const int inf = 1e+9;
int p1[maxn],p2[maxn],p3[maxn];
int dis[maxn], ans, cnt = 1, s, t, pre[maxn * 10], nxt[maxn * 10], h[maxn], v[maxn * 10];
queue<int> q;
void make(int x, int y, int z) {
pre[++cnt] = y, nxt[cnt] = h[x], h[x] = cnt, v[cnt] = z;
p1[cnt]=x; p2[cnt]=y; p3[cnt]=z;
pre[++cnt] = x, nxt[cnt] = h[y], h[y] = cnt;
p1[cnt]=y; p2[cnt]=x; p3[cnt]=z;
}
bool bfs() {
memset(dis, 0, sizeof dis);
q.push(s), dis[s] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = h[x]; i; i = nxt[i])
if (!dis[pre[i]] && v[i])
dis[pre[i]] = dis[x] + 1, q.push(pre[i]);
}
return dis[t];
}
int dfs(int x, int flow) {
if (x == t || !flow)
return flow;
int f = flow;
for (int i = h[x]; i; i = nxt[i])
if (v[i] && dis[pre[i]] > dis[x]) {
int y = dfs(pre[i], min(v[i], f));
f -= y, v[i] -= y, v[i ^ 1] += y;
if (!f)
return flow;
}
if (f == flow)
dis[x] = -1;
return flow - f;
}
int solve(int _s,int _t) {
s=_s;
t=_t;
ans = 0;
for (; bfs(); ans += dfs(s, inf));
return ans;
}
}
int n, m, s, t, t1, t2, t3, x[N],y[N];
int id[N];
struct pii {
int x,y;
bool operator < (const pii &b) {
if(x==b.x) return y<b.y;
else return x<b.x;
}
};
namespace color {
vector <int> g[N];
int c[N];
void make(int p,int q) {
g[p].push_back(q);
g[q].push_back(p);
}
void dfs(int p) {
for(int q:g[p]) if(c[q]==0) {
c[q]=3-c[p];
dfs(q);
}
}
void solve() {
for(int i=1;i<=n;i++) {
if(c[i]==0) {
c[i]=1;
dfs(i);
}
}
}
}
int p1[N],p2[N];
int main() {
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++) {
cin>>t1>>t2;
p1[i]=t1;
p2[i]=t2;
color::make(t1,t2);
}
color::solve();
for(int i=1;i<=m;i++) {
t1=p1[i];
t2=p2[i];
if(color::c[p1[i]]==2) swap(t1,t2);
id[i]=flow::cnt+1;
x[i]=t1;
y[i]=t2;
flow::make(t1,t2,1);
}
for(int i=1;i<=n;i++) {
if(color::c[i]==1) flow::make(n+1,i,1);
else flow::make(i,n+2,1);
}
flow::solve(n+1,n+2);
for(int i=1;i<=flow::cnt;i++) {
if(flow::v[i]!=0) scc::make(flow::p1[i],flow::p2[i]);
}
scc::solve(n+2);
vector <pii> vec;
for(int i=1;i<=m;i++) {
if(flow::v[id[i]]==0) if(scc::bel[x[i]]!=scc::bel[y[i]])
vec.push_back({min(x[i],y[i]),max(x[i],y[i])});
}
cout<<vec.size()<<endl;
sort(vec.begin(),vec.end());
for(int i=0;i<vec.size();i++) cout<<vec[i].x<<" "<<vec[i].y<<endl;
}