传送门
题解：
一个点满足条件则不在某个最大匹配中。
先求任意一个最大匹配，然后从每个不在匹配中的点再做一次，在队列中的都可以被替换掉。 用带花树即可。
不过带花树的板不能乱改啊，否则容易GG。
#include <bits/stdc++.h> using namespace std; const int RLEN=1<<18|1; inline char nc() { static char ibuf[RLEN],*ib,*ob; (ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob) ? -1 : *ib++; } inline int rd() { char ch=nc(); int i=0,f=1; while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();} while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();} return i*f; } const int N=2e3+50, M=2e6+50; int g[N],nt[M],vt[M],ec; int n,m,mate[N],pre[N],q[N],anc[N],id[N],win[N],r; inline int ga(int x) {return (anc[x]==x) ? x : (anc[x]=ga(anc[x]));} inline void add(int x,int y) {nt[++ec]=g[x]; g[x]=ec; vt[ec]=y;} inline int lca(int x,int y) { static int vis[N],vt; ++vt; while(x) { if(vis[x]==vt) return x; vis[x]=vt; x=ga(pre[mate[x]]); if(!x) swap(x,y); } } inline void group(int x,int f) { while(ga(x)^f) { int y=mate[x], z=pre[y]; if(ga(z)^f) pre[z]=y; if(id[y]) id[y]=0, q[++r]=y; if(id[z]) id[z]=0, q[++r]=z; anc[ga(x)]=ga(y); anc[ga(y)]=ga(z); x=z; } } inline void bfs(int x) { for(int i=1;i<=n;i++) anc[i]=i, id[i]=-1; q[r=1]=x; id[x]=0; pre[x]=0; for(int i=1;i<=r;i++) { int u=q[i]; for(int e=g[u];e;e=nt[e]) { int v=vt[e]; if(!~id[v]) { id[v]=1; pre[v]=u; if(!mate[v]) { while(u) { int t=mate[u]; mate[u]=v; mate[v]=u; v=t; u=pre[t]; } return; } id[mate[v]]=0; q[++r]=mate[v]; } else if(!id[v] && (ga(u)^ga(v))){ int l=lca(ga(u),ga(v)); if(ga(u)^l) pre[u]=v; if(ga(v)^l) pre[v]=u; group(u,l); group(v,l); } } } } inline void solve() { for(int i=1;i<=n;i++) mate[i]=0, win[i]=0, g[i]=0; n=rd(), m=rd(); ec=0; for(int i=1;i<=m;i++) { int x=rd(), y=rd(); add(x,y); add(y,x); } for(int i=1;i<=n;i++) if(!mate[i]) bfs(i); for(int i=1;i<=n;i++) if(!mate[i]) { win[i]=1; bfs(i); while(r) win[q[r--]]=1; } int ans=0; for(int i=1;i<=n;i++) ans+=win[i]; printf("%dn",ans); } int main() { for(int T=rd();T;T--) solve(); }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384
