当前位置 博文首页 > Implicit_的博客：经典算法:求解补图的连通块
从小到大遍历节点。set动态维护当前已有连通块。对于每新增的一个节点 i i i，我们试图用它来合并这些已有的连通块。具体做法就是用map记录它到每个连通块的边数。当连接边数 < 连通块点数时，合并 i i i与这个连通块。连完清空set,再重新更新最新父节点.
乍看复杂度很高，但是均摊下来可以接受。
1.想象我们开始有 n n n个连通块。然后逐渐两两合并这些连通块.最多合并 n ? 1 n-1 n?1次后成为一个连通块。往后就不可能再有合并连通块的情况了。所以总共合并 n ? 1 n-1 n?1次连通块,每次复杂度为 l o g n logn logn.总复杂度为 O ( n l o g n ) O(nlogn) O(nlogn).
2.当一个点 v v v不合并一个连通块时，一定是 v v v和这个连通块的所有点都有边。那么这种情况发生的次数最多就是边数 m m m次.
复杂度: O ( n l o g n + m ) O(nlogn+m) O(nlogn+m)
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int a[maxn];
int f[maxn] , sz[maxn];
int getf (int x) {return x == f[x] ? x : f[x] = getf(f[x]);}
bool mer (int a , int b)
{
int fa = getf(a) , fb = getf(b);
if (fa == fb) return false;
f[fb] = fa;
sz[fa] += sz[fb];
return true;
}
vi e[maxn];
int main()
{
ios::sync_with_stdio(false);
int n , m; cin >> n >> m;
for (int i = 1 ; i <= m ; i++){
int x , y; cin >> x >> y;
e[x].pb(y);
e[y].pb(x);
}
for (int i = 1 ; i <= n ; i++) f[i] = i , sz[i] = 1;
unordered_set<int> fa;
unordered_map<int,int> q;
for (int i = 1 ; i <= n ; i++){
q.clear();
for (auto v : e[i]) if (v < i) q[getf(v)]++;
for (auto g : fa) if (q[g] < sz[g]) mer(g , i);
unordered_set<int> tmp = fa;fa.clear();
for (auto g : tmp) fa.insert(getf(g));
if (getf(i) == i) fa.insert(i);
}
int ans = 0;
for (int i = 1 ; i <= n ; i++) if (getf(i) == i) ans++;
cout << ans - 1 << endl;
return 0;
}
做法：set维护当前未访问节点。从1到n,每个未访问的节点 x x x，做一次bfs将含它的最大连通块求出来。
具体的bfs,从 x x x开始，若 x x x和set中的某个点 y y y没边相连，就代表他们在补图中一定在一个集合里。所以将其插入队列，删掉set。如此往复这个过程即可。
对于bfs的每一次遍历set里的某一个元素时，有两种结果:
1.他们有边相连，无法将其删去.2.他们没边相连，可以将其删去.
对于情况1,它发生的次数就是边数的次数嘛.对于情况2,它最多就发生 n n n次嘛。每一次会删去一个点。最多删去 n n n个点.
复杂度： O ( m l o g m + n l o g n ) O(mlogm+nlogn) O(mlogm+nlogn)
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
set<int> s;
set<pii> e;
int vis[maxn];
void bfs (int x)
{
queue<int> q;
s.erase(x);
q.push(x);
vis[x] = 1;
while (q.size()){
int u = q.front();
q.pop();
for (auto it = s.begin() ; it != s.end();){
int v = *it++;
if (e.count(mp(u , v))) continue;
s.erase(v);
q.push(v);
vis[v] = 1;
}
}
return ;
}
int
