本文主要是介绍Connected Components? CodeForces - 920E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://codeforces.com/problemset/problem/920/E
求补图的各个连通块大小 智商不够 直接线段树优化建图 然后tarjan缩点 幸好内存不紧。。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn=2e5+10;
const int maxm=2e5+10;
const int N=0x3f3f3f3f;vector <int> edge[4*maxn];
vector <int> pre[maxn];
stack <int> stk;
int first[4*maxn],val[4*maxn],dfn[4*maxn],low[4*maxn],belong[4*maxn],book[4*maxn],sum[4*maxn],mp[maxn],ans[maxn];
int n,m,nn,num,cnt,tot;void build(int l,int r,int cur)
{int m;if(l==r){val[cur]=1,mp[l]=cur;nn=max(nn,cur);return;}edge[cur].pb(2*cur);edge[cur].pb(2*cur+1);m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);
}void update(int tar,int pl,int pr,int l,int r,int cur)
{int m;if(pl<=l&&r<=pr){edge[tar].pb(cur);return;}m=(l+r)/2;if(pl<=m) update(tar,pl,pr,l,m,2*cur);if(pr>m) update(tar,pl,pr,m+1,r,2*cur+1);
}void dfs(int cur)
{int i,v,t;stk.push(cur);dfn[cur]=num,low[cur]=num,book[cur]=1;num++;for(i=0;i<edge[cur].size();i++){v=edge[cur][i];if(!dfn[v]){dfs(v);low[cur]=min(low[cur],low[v]);}else if(book[v]) low[cur]=min(low[cur],low[v]);}if(dfn[cur]==low[cur]){cnt++;while(!stk.empty()){v=stk.top();stk.pop();book[v]=0;belong[v]=cnt;sum[cnt]+=val[v];if(cur==v) break;}}
}void tarjan()
{int u,v;num=1,cnt=0;for(u=1;u<=nn;u++) if(!dfn[u]) dfs(u);
}int main()
{int i,u,v,a,b;scanf("%d%d",&n,&m);build(1,n,1);for(i=1;i<=m;i++){scanf("%d%d",&u,&v);pre[u].pb(v),pre[v].pb(u);}for(u=1;u<=n;u++){pre[u].pb(u),pre[u].pb(0),pre[u].pb(n+1);sort(pre[u].begin(),pre[u].end());/*printf("***%d***\n",u);for(i=0;i<pre[u].size();i++) printf("%d ",pre[u][i]);printf("\n");*/for(i=0;i+1<pre[u].size();i++){a=pre[u][i],b=pre[u][i+1];if(a+1<=b-1) update(mp[u],a+1,b-1,1,n,1);}}tarjan();for(i=1;i<=cnt;i++) if(sum[i]!=0) ans[++tot]=sum[i];sort(ans+1,ans+tot+1);printf("%d\n",tot);for(i=1;i<=tot;i++) printf("%d ",ans[i]);printf("\n");return 0;
}/*
5 6
1 3
1 4
1 5
2 4
2 5
3 55 7
1 3
1 4
1 5
2 4
2 5
3 4
3 5
*/
这篇关于Connected Components? CodeForces - 920E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
