傳送門
文章目錄
題意：
n≤2e5,m≤2e5n\le2e5,m\le2e5n≤2e5,m≤2e5。
思路：
這是題是我上個題的一部分，算是個小知識點，暴力能過。
直接維護一個setsetset，讓后遍歷所有點，如果當前這個點沒有被遍歷，那么就放入隊列中，擴展出去，每個點最多入隊一次，而且邊數不會很多，復雜度大約是(n+m)logn(n+m)logn(n+m)logn
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,m
;
int p
[N
],se
[N
];
LL rest
;
bool st
[N
];
set
<int>v
[N
],all
;
struct Node
{int a
,b
,w
,flag
; bool operator < (const Node
&W
) const {return w
<W
.w
;}
}edge
[N
];int find(int x
) {return x
==p
[x
]? x
:p
[x
]=find(p
[x
]);
}void get_block() {queue
<int>q
;vector
<int>now
;for(int i
=1;i
<=n
;i
++) {if(!st
[i
]) {q
.push(i
); st
[i
]=1;all
.erase(i
);while(q
.size()) {int u
=q
.front(); q
.pop();now
.clear();for(auto x
:all
) {if(v
[u
].count(x
)) continue;q
.push(x
); now
.pb(x
);st
[x
]=1;int a
=find(u
),b
=find(x
);se
[a
]+=se
[b
];p
[b
]=a
;rest
--;}for(auto x
:now
) all
.erase(x
);}}}
}int main()
{
cin
>>n
>>m
;rest
=1ll*n
*(n
-1)/2-m
;for(int i
=1;i
<=n
;i
++) all
.insert(i
),p
[i
]=i
;for(int i
=1;i
<=m
;i
++) {int a
,b
; scanf("%d%d",&a
,&b
);v
[a
].insert(b
); v
[b
].insert(a
);}for(int i
=1;i
<=n
;i
++) p
[i
]=i
,se
[i
]=1;get_block();vector
<int>ans
;for(int i
=1;i
<=n
;i
++) if(i
==find(i
)) ans
.pb(se
[i
]);sort(ans
.begin(),ans
.end());printf("%d\n",ans
.size());for(auto x
:ans
) printf("%d ",x
);return 0;
}
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎
總結
以上是生活随笔為你收集整理的Educational Codeforces Round 37 (Rated for Div. 2) E. Connected Components? 暴力 + 补图的遍历的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
