发现题目给了一张补图，求的是最大团
而且隐隐约约告诉我们这张补图是一个二分图
于是非常自然联想到最大团等于补图最大独立集
最大独立集又等于总点数-最小点覆盖
最小点覆盖=最大匹配
使得最大团增加就需要使得最大匹配减小
于是我们终于读懂题目了，就是求二分图匹配的必须边
直接在残量网络里跑(tarjan)，就是如果这条边没有满流就连上
对于一条边((x,y))
如果((x,y))是一条匹配边或者(x)，(y)在同一个强联通分量里，那么这就是一条最大匹配的可行边
如果((x,y))是一条匹配边并且(x)，(y)不在同一个强连通分量里，那么这就是一条必须边
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#define re register
#define mp std::make_pair
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=12005;
const int inf=1e9;
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt,f;}e[500005];
int n,m,num=1,S,T;
std::queue<int> q;
int head[maxn],d[maxn],cur[maxn],co[maxn];
inline void C(int x,int y,int f) {
e[++num].v=y;e[num].f=f;
e[num].nxt=head[x];head[x]=num;
}
inline void add(int x,int y,int f) {C(x,y,f);C(y,x,0);}
inline int BFS() {
for(re int i=S;i<=T;i++) d[i]=0,cur[i]=head[i];
d[S]=1,q.push(S);
while(!q.empty()) {
int k=q.front();q.pop();
for(re int i=head[k];i;i=e[i].nxt)
if(!d[e[i].v]&&e[i].f) d[e[i].v]=d[k]+1,q.push(e[i].v);
}
return d[T];
}
int dfs(int x,int now) {
if(x==T||!now) return now;
int flow=0,ff;
for(re int& i=cur[x];i;i=e[i].nxt)
if(e[i].f&&d[e[i].v]==d[x]+1) {
ff=dfs(e[i].v,min(e[i].f,now));
if(ff<=0) continue;
now-=ff,flow+=ff,e[i].f-=ff,e[i^1].f+=ff;
if(!now) break;
}
return flow;
}
std::vector<int> ee[maxn];
namespace Tarjan {
std::vector<int> v[maxn];
int dfn[maxn],low[maxn],col[maxn],st[maxn],f[maxn];
int top,p,cnt,mid,tot;
std::pair<int,int> ans[150005];
void tarjan(int x) {
dfn[x]=low[x]=++cnt;
f[x]=1,st[++top]=x;
for(re int i=0;i<v[x].size();++i) {
int j=v[x][i];
if(!dfn[j]) tarjan(j),low[x]=min(low[x],low[j]);
else if(f[j]) low[x]=min(low[x],dfn[j]);
}
if(dfn[x]==low[x]) {
++p;
do {
mid=st[top--];
f[mid]=0;
col[mid]=p;
}while(mid!=x);
}
}
void solve() {
for(re int i=S;i<=T;i++)
for(re int j=head[i];j;j=e[j].nxt)
if(e[j].f) v[i].push_back(e[j].v);
for(re int i=S;i<=T;i++) if(!dfn[i]) tarjan(i);
for(re int i=1;i<=n;i++) {
if(co[i]) continue;
for(re int j=head[i];j;j=e[j].nxt)
if(col[i]!=col[e[j].v]&&!e[j].f&&e[j].v!=S) {
int xx=min(i,e[j].v);
int yy=max(i,e[j].v);
ans[++tot]=mp(xx,yy);
}
}
std::sort(ans+1,ans+tot+1);
printf("%d
",tot);
for(re int i=1;i<=tot;i++) printf("%d %d
",ans[i].first,ans[i].second);
}
}
void paint(int x,int c) {
co[x]=c;
for(re int i=0;i<ee[x].size();i++) {
int j=ee[x][i];
if(co[j]!=2) continue;
paint(j,c^1);
}
}
int main() {
n=read(),m=read();T=n+1;
for(re int x,y,i=1;i<=m;i++)
x=read(),y=read(),ee[x].push_back(y),ee[y].push_back(x);
for(re int i=1;i<=n;i++) co[i]=2;
for(re int i=1;i<=n;i++)
if(co[i]==2) paint(i,0);
for(re int i=1;i<=n;i++)
if(!co[i]) add(S,i,1);else add(i,T,1);
for(re int i=1;i<=n;i++) {
if(co[i]) continue;
for(re int j=0;j<ee[i].size();j++)
add(i,ee[i][j],1);
}
while(BFS()) dfs(S,inf);
Tarjan::solve();
return 0;
}