记录编号	201631	评测结果	WWWWWWWWWW
题目名称	游历校园	最终得分	0
用户昵称	明天	是否通过	未通过
代码语言	C++	运行时间	0.824 s
提交时间	2015-10-30 22:20:58	内存使用	8.80 MiB

#include <iostream>
#include <cstdio>
using namespace std;

struct node
{
	int x,next;
};
const int maxn=100000+1;
const int maxm=500000+1;

int n,m;
int h[maxn];
node table[maxm*2];
int len;
int ans;

int front,tail;
bool v[maxn];
int q[maxn];

void add1(int i,int j);
void spfa(int s);
int main()
{
	freopen("sent.in","r",stdin);
	freopen("sent.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for (int k=0; k<m; k++)
	{
		int i,j;
		scanf("%d%d",&i,&j);
		add1(i,j); add1(j,i);
	}
	
	for (int i=1; i<=n; i++)
	{
		if (!v[i])
		{
			ans++;
			spfa(i);
		}
	}
	printf("%d\n",ans-1);
	return 0;
}
void add1(int i,int j)
{
	len++;
	table[len].x=j; table[len].next=h[i];
	h[i]=len;
}
void spfa(int s)
{
	front=0; tail=1;
	q[tail]=s; v[s]=true;
	while (front != tail)
	{
		int x;
		front++;
		x=q[front];
		
		int p=h[x];
		while (p!=0)
		{
			int y=table[p].x;//x->y
			if (!v[y])
			{
				v[y]=true;
				tail++;
				q[tail]=y;
			}
			p=table[p].next;
		}
	}
}