CF292D Connected Components 解题报告_综合

CF292D Connected Components 解题报告

1 题目链接

https://codeforces.com/problemset/problem/292/D

2 题目整理

题目 : 连接组件

题目描述

我们已经知道Polycarpus担任系统管理员的大公司。那里的计算机网络由n台计算机和m根连接几对计算机的电缆组成。换言之，计算机网络可以表示为具有n个节点和m条边的无向图。让我们用1到n的整数来索引计算机，让我们用1到m的整数来索引电缆。

Polycarpus被赋予一项重要任务——检查公司网络的可靠性。为此，Polycarpus决定在计算机网络上进行一系列k实验，其中第i个实验如下：

暂时断开从 $l_i$ 到 $r_i$ （包含两边）的索引电缆（其他电缆保持连接）。
计算此时定义计算机网络的图形中连接组件的数量。
将断开的电缆与索引从 $l_i$ 重新连接到 $r_i$ （即恢复初始网络）。

帮助Polycarpus执行所有实验，并为每个实验打印定义计算机网络的图形中连接组件的数量。孤立顶点应计为单个组件。

输入格式

第一行包含两个空格分隔的整数n，m，分别对应计算机的数量和电缆的数量。

往下m行包含电缆的说明。第i行含有一对整数 $x_i，y_i$ ,表示第i根电缆连接的计算机编号。请注意，一对计算机可以通过多条电缆连接。

下一行包含整数k-实验次数。接下来的k行包含实验的描述。第i行包含空格分隔的整数 $l_i，r_i$ -第i次实验期间Polycarpus断开的电缆范
围。

输出格式

打印k个数字，第i个数字表示在第i个实验期间定义计算机网络的图形中连接组件的数量。

样例输入1

样例输出1

数据范围

对于 $100\%$ 的数据:

$\le n \le 500$
$\le m \le 10^4$
$\le x_i, y_i \le n$
$x_i \neq y_i$
$\le k \le 2 * 10^4$
$\le l_i, r_i \le m$

3 题意分析

3.1 题目大意

现有一个n个点，m条边的无向图，有k次询问，每次要求断开 $l_i$ 到 $r_i$ 的所有边后，图上剩余的连通快数量。

3.2 样例分析

如上所述。

4 解法分析

求连通块数量，很容易能想到并查集。但是并查集并不支持删除操作，所以我们要反向加边。然而，如果单纯用并查集来做这道题的话，时间复杂度为 $O(mk\log{n})$ ，想要过这一道题很悬。

所以，我们可以再进行一些优化。

因为题目中需要删除的边一定是连续编号的，所以可以想到运用前缀和来解决。先把左右两端的前缀和数组都建立起来，到每次查询时，就把两边的点拼在一起便解决了。这样一来，时间复杂度降为了 $O(nk\log{n})$ 。因为n很小，所以可以通过这一道题。

AC代码

ACCode #001

// From Heart_Blue
// Rating 2425
// reason : 思路清晰，代码简洁明了，运用了class
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;
pair<int, int> p[N];
class UnionFind
{
    int p[N];
public:void init(int n = N){
    memset(p, -1, sizeof(int)*n);}int Find(int x){
    int s = x;while (p[s] >= 0) s = p[s];while (x != s){
    int t = p[x];p[x] = s;x = t;}return s;}void Union(int x, int y){
    int px = Find(x);int py = Find(y);if (p[px] > p[py]) swap(px, py);p[px] += p[py];p[py] = px;}} uf;
int res[N];
vector<pair<int, int>> vp[N];
int main()
{
    //freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);int n, m;scanf("%d%d", &n, &m);int lo = n;uf.init(n + 1);for (int i = 1; i <= m; i++){
    scanf("%d%d", &p[i].first, &p[i].second);if (uf.Find(p[i].first) != uf.Find(p[i].second))uf.Union(p[i].first, p[i].second), lo--;}int q;scanf("%d", &q);for(int i =1; i <= q; i++){
    int l, r;scanf("%d%d", &l, &r);vp[l].push_back({
     r,i });}for (int i = 1; i <= m; i++){
    if (vp[i].empty()) continue;uf.init(n + 1);sort(vp[i].begin(), vp[i].end());int ans = n;for (int j = 1; j < i; j++){
    int x, y;tie(x, y) = p[j];if (uf.Find(x) != uf.Find(y))uf.Union(x, y), ans--;}int cur = m;while (!vp[i].empty()){
    int r, pos;tie(r, pos) = vp[i].back();vp[i].pop_back();while (cur > r && ans != lo){
    if (uf.Find(p[cur].first) != uf.Find(p[cur].second))uf.Union(p[cur].first, p[cur].second), ans--;cur--;}res[pos] = ans;}}for (int i = 1; i <= q; i++) printf("%d\n", res[i]);return 0;
}

ACCode #002

// From He_Ren
// Rating 3006
// reason : 思路清晰，代码简洁易懂通俗，可读性强
#include<cstdio>
const int MAXN = 5e2 + 5;
const int MAXM = 1e4 + 5;struct DSC
{
    int fa[MAXN];inline void init(int n){
     for(int i=1; i<=n; ++i) fa[i]=i;}int find(int u){
     return fa[u]==u? u: fa[u]=find(fa[u]);}inline void connect(int u,int v){
     fa[find(u)]=find(v);}	
}pre[MAXM],suf[MAXM];struct Edge
{
    int u,v;
}e[MAXM];int main(void)
{
    int n,m;scanf("%d%d",&n,&m);for(int i=1; i<=m; ++i)scanf("%d%d",&e[i].u,&e[i].v);pre[0].init(n);for(int i=1; i<=m; ++i){
    pre[i]=pre[i-1];pre[i].connect(e[i].u,e[i].v);}suf[m+1].init(n);for(int i=m; i>=1; --i){
    suf[i]=suf[i+1];suf[i].connect(e[i].u,e[i].v);}int Q;scanf("%d",&Q);while(Q--){
    int l,r;scanf("%d%d",&l,&r);DSC now=pre[l-1];for(int i=1; i<=n; ++i)now.connect(now.fa[i], suf[r+1].fa[i]);int cnt=1;for(int i=2; i<=n; ++i)if(now.find(i) != now.find(1))++cnt,now.connect(i,1);printf("%d\n",cnt);}return 0;
}

ACCode #003

// From andrey-tsb
// Rating 2010
// reason : 思路清晰，代码清奇，用到了memcpy
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;int pref[10010][510];
int suff[10010][510];
int cur[510];
int fl[510];int findx(int x, int* p)
{
    if (p[x] == x)return x;return p[x] = findx(p[x], p);
}void unite(int a, int b, int *p)
{
    int pa = findx(a, p);int pb = findx(b, p);if (pa==pb)return;if (rand()&1)p[pa] = pb;elsep[pb] = pa;
}int main()
{
    // freopen("/home/stranger/qworkspace/Test3/input.txt","r",stdin);int n,m,k;cin >> n >> m;vector<pair<int,int> > mas(m);for (int i=0;i<m;i++){
    cin >> mas[i].first >> mas[i].second;mas[i].first--;mas[i].second--;}for (int i=0;i<n;i++)suff[m+1][i] = pref[0][i] = i;for (int i=1;i<=m;i++){
    memcpy(pref[i], pref[i-1], sizeof(pref[i]) );unite(mas[i-1].first, mas[i-1].second, pref[i]);}for (int i=m;i>=1;i--){
    memcpy(suff[i], suff[i+1], sizeof(suff[i]));unite(mas[i-1].first, mas[i-1].second, suff[i]);}cin >> k;for (int i=0;i<k;i++){
    int a,b;cin >> a >> b;memcpy(cur, pref[a-1], sizeof(cur));for (int j=0;j<n;j++)unite(j, findx(j, suff[b+1]), cur);int cnt = 0;for (int j=0;j<n;j++){
    int pr = findx(j, cur);if (!fl[pr])cnt++;fl[pr] = true;}memset(fl, 0, sizeof(fl));cout << cnt << "\n";}return 0;
}

5 结语

update 2022.7.21
这里，提一下并查集的时间复杂度。经过优化（路径压缩，按秩合并）的并查集单次时间复杂度是 $O(\log{n})$ ，而不加优化的并查集是 $O (n)$ ，所以这题是需要优化的 $QwQ$ （不加优化 $O(n^2k)$ 你可以试试看:-）)
此题似乎还有莫队的做法，但蒟蒻无能为力，只好放一个链接了。
最后的最后，我要感谢一个大佬yh2021SYXMZ和我一起讨论关于并查集的时间复杂度问题，指正了我博客中时间复杂度的错误。