给定一个可以划分为不超过两个团的稠密图，以补图的形式描述。求有多少对点满足在它们之间建边后最大团的大小会增加。\(n \leq 10^4, m \leq 1.5\times 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;}