pypy3 解法, 执行用时: 1700ms, 内存消耗: 55312K, 提交时间: 2021-11-07 19:16:45

def getint():
    return [int(i) for i in input().split()]
n,m=getint()
a=[0]*(n+1)
for i in range(1,n+1):
    a[i]=i
def find(x):
    if a[x]==x:
        return x
    else:
        a[x]=find(a[x])
        return a[x]
def union(x,y):
    a[find(x)]=find(y)
for i in range(m):
    x,y=getint()
    union(x,y)
#print(a)
x=find(1)
#print("x:",x)
ans=0
for i in range(1,n+1):
    if find(a[i])==x:
        ans+=1
        #print(i)
print(ans)

C++(clang++11) 解法, 执行用时: 448ms, 内存消耗: 8220K, 提交时间: 2021-04-05 16:14:23

#include <bits/stdc++.h>
using namespace std;
int n,m,p,a,b,f[2000001],i,t=1;
int find(int x)
{	
    if(f[x]==x)return x;
	return f[x]=find(f[x]);
}
int main()
{
	cin>>n>>m;
	for(i=1;i<=n;i++)
		f[i]=i;
	for(i=1;i<=m;i++)
	{
        cin>>a>>b;
		f[find(a)]=find(b);	
	} 
	for(i=2;i<=n;i++)
		if(find(1)==find(i))
			t++;
	cout<<t;			
	return 0;	
}