C++ 解法, 执行用时: 58ms, 内存消耗: 460KB, 提交时间: 2021-12-03

#include<bits/stdc++.h>
using namespace std;
class Union {
public:
    int p[10001];
    int find(int x) {
        if (x != p[x])
            p[x] = find(p[x]);
        return p[x];
    }
};

int main() {
    int n, idx, m;
    cin>>n>>idx>>m;
    Union u;
    for (int i = 0; i < n; i++)
        u.p[i] = i;
//     for(int i=0;i<n;i++)u.p[i]=i;
    int ans=0,b=0;
    while(m--){
        int one,two;
        scanf("%d,%d",&one,&two);
        if(one==idx||two==idx)b++;
        int fx=u.find(one),fy=u.find(two);
        if(fx!=fy)u.p[fx]=fy;
    }
    for(int i=0;i<n;i++){
        if(u.find(idx)==u.find(i))ans++;
    }
    cout<<ans-b-1<<endl;
//     for (int i = 0; i < n; i++)
//         u.p[i] = i;
//     int i, j;
//     char c;
//     int cnt = 0;
//     for (int i = 0; i < m; i++) {
//         cin>>i>>c>>j;
//         if (i == idx || j == idx)
//             cnt--;
//         if (u.find(i) != u.find(j)) {
//             u.p[u.find(i)] = u.p[u.find(j)];
//         }
//     }

//     for (int i = 0; i < n; i++) {
//         if (u.find(idx) == u.find(i))
//             cnt++;
//     }
//     cout<<cnt-1<<endl;
}

C++ 解法, 执行用时: 58ms, 内存消耗: 576KB, 提交时间: 2021-09-06

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,root,m;
int pre[N],sz[N];
int find(int x){
    if(pre[x]==x)    return x;
    return pre[x]=find(pre[x]);
}
int main(){
    scanf("%d%d%d",&n,&root,&m);
    root++;
    for(int i=1;i<=n;i++){
        pre[i]=i;
        sz[i]=1;
    }
    int cnt=0;
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d,%d",&u,&v);
        u++;    v++;
        if(u==root||v==root)    cnt++;
        int fx=find(u),fy=find(v);
        if(fx!=fy){
            pre[fx]=fy;
            sz[fy]+=sz[fx];
        }
    }
    //cout<<sz[find(root)]<<" "<<cnt<<'\n';
    printf("%d\n",sz[find(root)]-cnt-1);
    return 0;
}

C++ 解法, 执行用时: 59ms, 内存消耗: 572KB, 提交时间: 2021-09-20

//并查集基本应用，最后别忘了减掉本身
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,ix,m;
vector<int>f;
int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);
}
int main(void){
    cin>>n>>ix>>m;
    f=vector<int>(n);
    for(int i=0;i<n;i++)f[i]=i;
    int ans=0,b=0;
    while(m--){
        int one,two;
        scanf("%d,%d",&one,&two);
        if(one==ix||two==ix)b++;
        int fx=find(one),fy=find(two);
        if(fx!=fy)f[fx]=fy;
    }
    for(int i=0;i<n;i++){
        if(find(ix)==find(i))ans++;
    }
    cout<<ans-b-1<<endl;
    return 0;

}

C++ 解法, 执行用时: 60ms, 内存消耗: 504KB, 提交时间: 2021-09-05

#include <bits/stdc++.h>
using namespace std;
int f[10001];
int getRoot(int x) {
    int rx = x;
    while (-1 != f[rx]) rx = f[rx];
    if (x != rx) f[x] = rx;
    return rx;
}
void merge(int x, int y) {
    int rx=getRoot(x), ry=getRoot(y);
    if (rx!=ry) f[rx] = ry;
}
int main() {
    int n, a, m, l, r;
    scanf("%d%d%d", &n, &a, &m);
    memset(f, -1, sizeof f);
    int res = -1;
    for (int i = 0; i < m; ++i) {
        scanf("%d,%d", &l, &r);
        if (l == r) continue;
        if (l == a || r == a) --res;
        merge(l, r);
    }
    int ra = getRoot(a);
    for (int i = 0; i < n; ++i) {
        if (ra == getRoot(i)) ++res;
    }
    printf("%d\n", res);
    return 0;
}

C++ 解法, 执行用时: 61ms, 内存消耗: 412KB, 提交时间: 2021-10-12

//并查集基本应用，最后别忘了减掉本身
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,ix,m;
vector<int>f;
int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);
}
int main(void){
    cin>>n>>ix>>m;
    f=vector<int>(n);
    for(int i=0;i<n;i++)f[i]=i;
    int ans=0,b=0;
    while(m--){
        int one,two;
        scanf("%d,%d",&one,&two);
        if(one==ix||two==ix)b++;
        int fx=find(one),fy=find(two);
        if(fx!=fy)f[fx]=fy;
    }
    for(int i=0;i<n;i++){
        if(find(ix)==find(i))ans++;
    }
    cout<<ans-b-1<<endl;
    return 0;

}