sienyu @ 2024-07-26 15:43:46

by sienyu @ 2024-07-26 15:45:05

怎么我的代码成这样了？？？

by Obijeb @ 2024-07-26 15:57:25

@sienyu 大抵是底下的三个反引号挂掉了

by Obijeb @ 2024-07-26 16:03:13

#include<bits/stdc++.h>

#define endl '\n'

using namespace std; //离线 逆向并查集

const int N = 2e5 + 10;

int root[N << 1]; // root数组

int n, m, k;

struct Edge {
    int x, y, i; // 当前边的起始终止节点 编号 
}
edge[N << 1];
bool isBroken[N << 1]; //标记当前节点有无被破坏 
vector < int > broken; //保存被破坏的节点 
vector < int > res;
vector < int > graph[N << 1];
int findRoot(int x) { //寻找x的根节点 
    if (root[x] == x) return x;
    else return root[x] = findRoot(root[x]);
}
void merge(int x, int y) { //将x, y进行合并 
    x = findRoot(x);
    y = findRoot(y);
    if (x != y) {
        root[x] = y; // x 的根节点修改为 y 
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) root[i] = i; // 并查集的初始化 
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x); // 无向图 
        edge[i] = {
            x,
            y,
            i
        };
    }
    cin >> k;
    for (int i = 1; i <= k; i++) {
        int t;
        cin >> t;
        isBroken[t] = 1; // t号节点被破坏 
        broken.push_back(t); //保存被破坏的节点离线处理 
    } // 任意两个节点之间没有联通 
    int total = n - k; //每建立一条边 则联通块的数量 - 1 所有节点被破坏后的联通块个数 
    for (int i = 1; i <= m; i++) {
        int x = edge[i].x;
        int y = edge[i].y; // x, y 均没有被破坏 且 x, y的根节点不同 
        int x_root = findRoot(x);
        int y_root = findRoot(y);
        if ((!isBroken[x] && !isBroken[y]) && (x_root != y_root)) {
            total--;
            merge(x, y);
        }
    } //此时total 为摧毁所有节点后的连通块 
    res.push_back(total);
    for (int i = broken.size() - 1; i >= 0; i--) { //将此时被摧毁的节点修复 
        int s = broken[i]; // 把s节点修复 看可以添加多少条边 
        int s_root = findRoot(s);
        isBroken[s] = 0;
        total++;
        for (int i = 0; i < graph[s].size(); i++) {
            int to = graph[s][i]; //所到达的点 
            if (!isBroken[to] && (s_root != findRoot(to))) {
                total--; //添加一条边则联通数 - 1; 
                if (total <= 1) total = 1;
                merge(s, to);
            }
        }
        res.push_back(total);
    } //res 数组逆向打印 
    for (int i = res.size() - 1; i >= 0; i--) cout << res[i] << endl;
    return 0;
}

by sienyu @ 2024-07-26 16:47:48

@Obijeb 这题恶心死我了

by Obijeb @ 2024-07-26 16:52:26

@sienyu 改好了

#include<bits/stdc++.h>

#define endl '\n'

using namespace std; //离线 逆向并查集

const int N = 2e5 + 10;

int root[N << 1]; // root数组

int n, m, k;

struct Edge {
    int x, y, i; // 当前边的起始终止节点 编号 
}
edge[N << 1];
bool isBroken[N << 1]; //标记当前节点有无被破坏 
vector < int > broken; //保存被破坏的节点 
vector < int > res;
vector < int > graph[N << 1];
int findRoot(int x) { //寻找x的根节点 
    if (root[x] == x) return x;
    else return root[x] = findRoot(root[x]);
}
void merge(int x, int y) { //将x, y进行合并 
    x = findRoot(x);
    y = findRoot(y);
    if (x != y) {
        root[x] = y; // x 的根节点修改为 y 
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) root[i] = i; // 并查集的初始化 
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x); // 无向图 
        edge[i] = {
            x,
            y,
            i
        };
    }
    cin >> k;
    for (int i = 1; i <= k; i++) {
        int t;
        cin >> t;
        isBroken[t] = 1; // t号节点被破坏 
        broken.push_back(t); //保存被破坏的节点离线处理 
    } // 任意两个节点之间没有联通 
    int total = n - k; //每建立一条边 则联通块的数量 - 1 所有节点被破坏后的联通块个数 
    for (int i = 1; i <= m; i++) {
        int x = edge[i].x;
        int y = edge[i].y; // x, y 均没有被破坏 且 x, y的根节点不同 
        int x_root = findRoot(x);
        int y_root = findRoot(y);
        if ((!isBroken[x] && !isBroken[y]) && (x_root != y_root)) {
            total--;
            merge(x, y);
        }
    } //此时total 为摧毁所有节点后的连通块 
    res.push_back(total);
    for (int i = broken.size() - 1; i >= 0; i--) { //将此时被摧毁的节点修复 
        int s = broken[i]; // 把s节点修复 看可以添加多少条边 
        int s_root = findRoot(s);
        isBroken[s] = 0;
        total++;
        for (int i = 0; i < graph[s].size(); i++) {
            int to = graph[s][i]; //所到达的点 
            if (!isBroken[to] && (findRoot(s) != findRoot(to))) {
                total--; //添加一条边则联通数 - 1; 
                if (total <= 1) total = 1;
                merge(s, to);
            }
        }
        res.push_back(total);
    } //res 数组逆向打印 
    for (int i = res.size() - 1; i >= 0; i--) cout << res[i] << endl;
    return 0;
}

只改了合并前的判断

by sienyu @ 2024-07-26 18:08:30

@Obijeb 我去，大佬牛逼！！！我知道为啥了，下面有个merge， s的根是会变化的，所以每一次都要去查询