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();
}
原文链接: https://www.cnblogs.com/cjoierShiina-Mashiro/p/12905741.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/349160
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!