首页 > 代码库 > bzoj1098题解

bzoj1098题解

2024-09-12 06:32:55   207人阅读

【题意分析】

　　给你一张无向图，求其补图的联通块数及各个联通块大小。

【解题思路】

　　暴搜！

　　然而n2会T怎么办？

　　仔细观察发现m远小于n2，也就是说这是一张极其稠密的补图。

　　这时就要用到黑科技了：floodfill！

　　用邻接表维护原图的边，用链表维护当前剩余可选点，每次从队首出发从链表里找补图的边，把这些边对应的点入队并从链表里删去。

　　这样，我们构造一种最坏的情况来卡这个算法：

　　假设前m/n个点每个点都只和一个点不相连，这样对于每个点都要遍历链表中的所有点，此时复杂度是O((m/n)*n)=O(m)。

　　因为前面已经把m条边都分配完了，接下来的第一个点就O(n)把链表清空了。之后的点全都是O(1)发现链表已被清空。

　　这样总复杂度就是O(m+n)了。

【参考代码】

技术分享
 1 #include <bits/stdc++.h> 2 #define range(i,c,o) for(register int i=(c);i<(o);++i) 3 #define dange(i,c,o) for(register int i=(c);i>(o);--i) 4 #define forin(i,t,p) for(t::        iterator i=p. begin();i!=p. end();++i) 5 #define dorin(i,t,p) for(t::reverse_iterator i=p.rbegin();i!=p.rend();++i) 6 using namespace std; 7   8 #define __debug 9 #ifdef __debug10     #define Function(type) type11     #define Procedure      void12 #else13     #define Function(type) __attribute__((optimize("-O2"))) inline type14     #define Procedure      __attribute__((optimize("-O2"))) inline void15 #endif16  17 #ifdef __int128_t18     typedef __int128_t integer;19 #else20     typedef long long integer;21 #endif22  23 //quick_io {24 Function(integer) getint()25 {26     char c=getchar(); for(;!isdigit(c)&&c!=‘-‘;c=getchar());27     short s=1; for(;c==‘-‘;c=getchar()) s*=-1; integer r=0;28     for(;isdigit(c);c=getchar()) (r*=10)+=c-‘0‘; return s*r;29 }30 //} quick_io31  32 static int n=getint();33  34 //list {35 int suc[100005],pre[100005];36 Procedure clear()37 {38     range(i,1,n+1) suc[i]=i+1,pre[i]=i-1;39     suc[0]=1,pre[n+1]=n;40 }41 Procedure erase(const int&x)42 {43     pre[suc[x]]=pre[x],suc[pre[x]]=suc[x];44 }45 //} list46  47 bool tag[100005]={0},vis[100005]={0};48 vector<int> edg[100005]; queue<int> que;49 Function(int) floodfill(const int&rt)50 {51     int ret=0; erase(rt);52     for(que.push(rt);!que.empty();que.pop())53     {54         int fr=que.front(); vis[fr]=1,++ret;55         forin(i,vector<int>,edg[fr]) tag[*i]=1;56         for(int i=suc[0];i<=n;i=suc[i])57         {58             if(!tag[i]) erase(i),que.push(i);59         }60         forin(i,vector<int>,edg[fr]) tag[*i]=0;61     }62     return ret;63 }64  65 int rec[100005];66 int main()67 {68     for(int m=getint();m--;)69     {70         int u=getint(),v=getint();71         edg[u].push_back(v),edg[v].push_back(u);72     }73     clear(); int cnt=0;74     range(i,1,n+1) if(!vis[i]) rec[cnt++]=floodfill(i);75     sort(rec,rec+cnt),printf("%d\n",cnt);76     range(i,0,cnt) printf("%d ",rec[i]);77     return putchar(‘\n‘),0;78 }
View Code

 

bzoj1098题解


联系
我们