tj

好是91秒用78成功做出

#include<bits/stdc++.h>
using namespace std;
int fa[1000000];
int n,m;
int get(int x){
	if(fa[x]==x) 
		return x;
	return fa[x]=get(fa[x]);//优化
}
void merge(int x, int y)
{
	fa[get(x)]=get(y);
}

int main(){
	int n;
	while(cin>>n&&n)
	{
		for(int i=1;i<=n;i++)
			fa[i]=i;
		int m;
		cin>>m;
		for(int i=0;i<m;i++){
			int x,y;
			cin>>x>>y;
			if(get(x)!=get(y))
				merge(x,y);
		}
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			if(fa[i]==i)
				sum++;
		}
		cout<<sum-1<<endl;
	}
}