Codechef JERRYTOM Tom and Jerry

Link
不难发现答案就是该弦图的团数。
求团数可以用MCS算法，也可以按当前度数从小到大枚举一个点并删去其所有边，删完所有点时的度数就是答案。

#include<set>
#include<cctype>
#include<cstdio>
#include<vector>
#include<cstring>
#include<utility>
using pi=std::pair<int,int>;
const int N=100007;
char ibuf[1<<25|1],*iS=ibuf;int deg[N],vis[N];std::vector<int>e[N];std::multiset<pi>s;
int read(){int x=0;while(isspace(*iS))++iS;while(isdigit(*iS))(x*=10)+=*iS++&15;return x;}
void solve()
{
    int n=read(),m=read();
    memset(deg+1,0,4*n),memset(vis+1,0,4*n),s.clear();
    for(int i=1;i<=n;++i) e[i].clear();
    for(int i=1,u,v;i<=m;++i) ++deg[u=read()],++deg[v=read()],e[u].push_back(v),e[v].push_back(u);
    for(int i=1;i<=n;++i) s.emplace(deg[i],i);
    for(int ans=2;;++ans)
    {
	while(!s.empty()&&s.begin()->first<ans)
	{
	    int u=s.begin()->second;s.erase(s.begin()),vis[u]=1;
	    for(int v:e[u]) if(!s.empty()&&!vis[v]) s.erase(s.find({deg[v],v})),s.emplace(--deg[v],v);
	}
	if(s.empty()) {printf("%d\n",ans);break;}
    }
}
int main()
{
    fread(ibuf,1,1<<25,stdin);
    for(int t=read();t;--t) solve();
}

Codechef JERRYTOM Tom and Jerry

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12905741.html