俺的图图呢

第一行三个整数 $n,m,k$ ，含义如题面所述。
第二行 $k$ 个整数 $s_1,s_2,\cdots,s_k$ ，表示 $k$ 个关键点。
接下来 $m$ 行，每行三个整数 $x,y,w$ ，表示一条在结点 $x$ 和 $y$ 之间，边权为 $w$ 的无向边。
（ $1\leqslant n \leqslant 10^5,1\leqslant m\leqslant 2\times 10^5,1 \leqslant w \leqslant 10^9, 2 \leqslant k \leqslant 10^5$ ，没有自环和重边）

C++(g++ 7.5.0) 解法, 执行用时: 214ms, 内存消耗: 7076K, 提交时间: 2022-11-22 12:05:43

#include<bits/stdc++.h>
using namespace std;
vector<int> e[100010];
int vis[100010], a[100010];
int n, m, k;
void dfs(int u)
{
    vis[u] = 1;
    for (int v : e[u]) {
        if (!vis[v]) dfs(v);
    }
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int res = 0;
    for (int i = 1; i <= k; i++) {
        if (!vis[a[i]]) {
            res++;
            dfs(a[i]);
        }
    }
    cout << res;
    return 0;
}

C++ 解法, 执行用时: 66ms, 内存消耗: 1016K, 提交时间: 2021-12-13 17:44:19

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,k,f[N],s[N];
bool vs[N];
int find(int u){
    return (u==f[u])?u:(f[u]=find(f[u]));
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++) scanf("%d",&s[i]);
    for(int i=1;i<=n;i++) f[i]=i;
    while(m--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        u=find(u); v=find(v);
        f[v]=u;
    }
    //for(int i=1;i<=n;i++) cout<<find(i)<<endl;
    int c=0;
    for(int i=1;i<=k;i++) if(!vs[find(s[i])]){
        vs[find(s[i])]=1; c++;
    }
    cout<<c<<endl;
}

详情