C++ 无向图 判断连通性

Question

问题描述
给定一个无向图和依次应用于该图的查询。
有两种类型的查询。

cut - 切断图，即删除一条边。
ask - 检查两个顶点是否连通。
在所有的切割操作之后，图中将没有留下任何边。
你要找到所有ask查询的正确答案。
输入：
• 一行包括n,m和k (1 ≤ n ≤ 5 · 10^4, 0 ≤ m ≤ k ≤ 1.5 · 10^5) 分别代表顶点，边以及查询的数量。
• m行描述图的边，第i行包括ui 和 vi(1 ≤ ui, vi ≤ n)：是与第i条边相联系的顶点的指数，该图不包含循环和重复的边。
• k行查询。
– 一个 cut-类型的查询需输入： “cut u v” (1 ≤ u, v ≤ n), 代表要切掉u和v之间的线。
– 一个 ask-类型的查询需输入： “ask u v” (1 ≤ u, v ≤ n), 代表你要查询u和v此时是否处于相同的连接部分，也就是连通性。
注意：可以保证每条边在cut查询中只出现一次

输出：
对于每一个ask查询，如果顶点在同一个连通的组件中，则输出答案 “YES”，否则输出 “NO”。
答案的顺序应与输入中的ask查询顺序相同。

Answer 1

 
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<tuple<string, int, int> > vs;//存询问,离线处理
    vector<vector<int> > g(n);//邻接表存图
    vector<int> s(n);//集合
    for(int i=0;i<n;i++) s[i] = i;
    for(int i=0;i<m;i++){//存图
        int u, v;
        cin >> u >> v;
        u -= 1;
        v -= 1;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    function<int(int)> FIND = [&](int x){
        return x == s[x] ? x : s[x] = FIND(s[x]);//并查集
    };
    while(k--){
        string s;
        int u, v;
        cin >> s >> u >> v;
        u -= 1;
        v -= 1;
        vs.push_back(make_tuple(s, u, v));//存询问
    }
    reverse(vs.begin(), vs.end());//将询问倒过来
    vector<bool> ans;//存答案
    for(auto i : vs){
        if(get<0>(i)[0] == 'c'){//cut
            int u = get<1>(i);
            int v = get<2>(i);//一条边的起始顶点
            u = FIND(u);
            v = FIND(v);
            if(u == v) continue;
            s[u] = v;//并查集基本操作
        }else{
            int u = get<1>(i);
            int v = get<2>(i);
            if(FIND(u) == FIND(v)) ans.push_back(true);//如果u,v在同一个集合里
            else ans.push_back(false);
        }
    }
    reverse(ans.begin(), ans.end());//答案倒过来
    for(auto i : ans){
        if(i) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}