cpp 代码

#include<iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <list>
#include <functional>
#include <algorithm>
#include <memory>
#include <numeric>
#include <unordered_set>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int a[200010];
int p[200010];
int find(int x){
    if(p[x]!=x){
        p[x] = find(p[x]);
    }
    return p[x];
}

int main(){
    int _t = 1;
//    cin>>_t;
    while(_t--) {

        int n,m,q;cin>>n>>m>>q;
        unordered_map<int,unordered_set<int>> gra;
        unordered_map<int,unordered_set<int>> old_gra;
        int id = 1;
        iota(p+1,p+1+200000,1);
        unordered_map<int,int> map_person;
        for(int i = 1;i<=m;i++){
            int u,v;scanf("%d %d",&u,&v);
            if(!map_person.count(u))map_person[u] = id++;
            if(!map_person.count(v))map_person[v] = id++;
            gra[map_person[u]].insert(map_person[v]);
            gra[map_person[v]].insert(map_person[u]);
            old_gra[map_person[u]].insert(map_person[v]);
            old_gra[map_person[v]].insert(map_person[u]);
        }
        vector<vector<int>> actions;

        for(int i = 1;i<=q;i++){
            int ty,u,v;scanf("%d %d %d",&ty,&u,&v);
            actions.push_back({ty,u,v});
            if(ty==1){
                if(map_person.count(u) && map_person.count(v)) {
                    if (old_gra[map_person[u]].count(map_person[v])) {
                        gra[map_person[u]].erase(map_person[v]);
                        gra[map_person[v]].erase(map_person[u]);
                    }
                }
            }
        }

        for(auto &[u,gu]:gra){
            for(auto &v:gu){
                p[find(u)] = find(v);
            }
        }
        vector<string> res;
        for(int i = actions.size()-1;i>=0;i--){
            int ty = actions[i][0],u = actions[i][1],v = actions[i][2];
            if(ty == 2){

                if(map_person.count(u) && map_person.count(v)){
                    int mu = map_person[u],mv = map_person[v];
                    if(find(mu) == find(mv)){
                        res.push_back("Yes");
                    }
                    else res.push_back("No");
                }else{
                    res.push_back("No");
                }
            }
            else{
                if(map_person.count(u) && map_person.count(v)){
                    int mu = map_person[u],mv = map_person[v];
                    if(old_gra[mu].count(mv)){
                        p[find(mu)] = find(mv);
                    }
                }


            }
        }

        for(int i = res.size()-1;i>=0;i--){
            cout<<res[i]<<endl;
        }

    }

    return 0;
}

//1 2
//2 3
//4 5
//1 1 5
//2 1 3
//2 1 4
//1 1 2
//2 1 3

java

#include<bits/stdc++.h>
using namespace std;
int w[4];
unordered_set<int>st;
unordered_map<int,int>mp{{2,5},{5,2},{6,9},{9,6}};
vector<int>res;
bool vis[4];
void dfs(int u,int sum,int len){
    if(u==len){
        res.push_back(sum);
    }
    for(int i=0;i<4;i++){
        if(vis[i])continue;
        int x=w[i];
        vis[i]=true;
        dfs(u+1,sum*10+x,len);
        if(mp.count(x)){
            dfs(u+1,sum*10+mp[x],len);
        }
        vis[i]=false;

    }
}
int main(){
    for(int i=0;i<4;i++){
        scanf("%d,",&w[i]);
        st.insert(w[i]);
    }
    sort(w,w+4);
    int n=w[3];
    if(st.count(2)&&st.count(5)||st.count(6)&&st.count(9)||st.count(0)){
        puts("-1");
    }
    else{
        for(int len=1;len<=4;len++){
            dfs(0,0,len);
        }
        set<int>s(res.begin(),res.end());
        res.assign(s.begin(),s.end());
        int m=res.size();
        if(n<m)cout<<res[n-1]<<endl;
        else cout<<res.back()<<endl;
    }
    return 0;
}

python

n,m,q = map(int, input().split())
fa = {}

def find(x):
    if x == fa[x]: return x
    fa[x] = find(fa[x])
    return fa[x]

def union(x,y):
    if u not in fa: fa[u] = u
    if v not in fa: fa[v] = v
    fa[find(x)] = find(y)


edges = set()

for _ in range(m):
    u,v = map(int, input().split())
    if u not in fa: fa[u] = u
    if v not in fa: fa[v] = v
    edges.add((u,v))

ops = []
del_edges = set()
for _ in range(q):
    op,u,v = map(int, input().split())
    ops.append([op,u,v])
    if op == 1:
        if (u,v) in edges:
            del_edges.add((u,v))
        if (v,u) in edges:
            del_edges.add((v,u))

# 逆向构图
for u,v in edges:
    if (u,v) in del_edges or (v,u) in del_edges:
        # 要删除的边
        continue
    union(u,v)

ans = []
#逆向遍历
for i in range(q-1,-1,-1):
    op,u,v = ops[i]
    if op == 2:
        if u in fa and v in fa and find(u) == find(v):
            ans.append("Yes")
        else:
            ans.append("No")
    else:
        union(u,v)
ans.reverse()
for a in ans:
    print(a)

题目描述

小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢变淡的，最终朋友关系就淡忘了 现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识?

事件共有2种: 1u v:代表编号u的人和编号v的人淡忘了他们的朋友关系。 2 u v:代表小美查询编号u的人和编号v的人是否能通过朋友介绍互相认识. 注:介绍可以有多层，比如2号把1号介绍给3号，然后3号再把1号介绍给4号，这样1号和 4 号就认识了。

输入描述

第一行输入三个正整数$n,m,q$，代表总人数，初始的朋友关系数量，发生的事件数量

接下来的$m$行，每行输入两个正整数$u,v$、，代表切始编号$u$的人和编号$v$的人是朋友关系

接下来的$q$行，每行输入三个正整数$op,u,v$，含义如题目描述所述，

$1\le n\le 10^9$

$1\le m,q\le 10^5$

$1\le u,v\le n$

$1\le op\le 2$

输出描述

对于每次2号操作，输出一行字符用代表查询的答案。

如果编号$u$的人和编号$v$的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"No"

样例

输入

5 3 5
1 2
2 3
4 5
1 1 5
2 1 3
2 1 4
1 1 2
2 1 3

输出

Yes
No
No