Immortal Grass

第一行输入三个整数n，m，k，分别表示建筑的数量，道路的数量，以及Vanis面前的建筑物的编号，相邻整数间使用一个空格符分隔。
接下来输入m行，每行包含两个正整数，之间使用一个空格符分隔，将这种输入开始的第i行的两个整数记作 $u_i$ 和 $v_i$ ，表示 $u_i$ 与 $v_i$ 之间有一条无向边。

数据规范：
* $1 \le n \le 10^5$ .
* $0 \le m \le \min(\frac{n(n - 1)}{2},\ 10^5)$ .
* $1 \le k \le n$ .
* $1 \le u_i,\ v_i \le n$ .
* $u_i \ne v_i$ .
* 保证无重边和自环。
* 保证所有输入都是整数。

C++14(g++5.4) 解法, 执行用时: 35ms, 内存消耗: 2020K, 提交时间: 2019-12-07 13:14:52

#include<bits/stdc++.h>
using namespace std;
int fa[100010],sz[100010],n,m,k;
int ask(int x){
    return x==fa[x]?x:fa[x]=ask(fa[x]);
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;++i) fa[i]=i,sz[i]=1;
    for (int i=1,x,y;i<=m;++i){
        scanf("%d%d",&x,&y);
        int lx=ask(x),ly=ask(y);
        if (lx==ly) continue;
        sz[lx]+=sz[ly];
        fa[ly]=lx;
    }
    printf("%d\n",sz[ask(k)]);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 34ms, 内存消耗: 1508K, 提交时间: 2019-12-07 12:35:27

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,m,k,fa[MAXN];

int findfa(int x) {return x==fa[x]?x:fa[x]=findfa(fa[x]);}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		fa[findfa(u)]=fa[findfa(v)];
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(findfa(i)==findfa(k))
			ans++;
	printf("%d\n",ans);
	return 0;
}

详情