学步园

题目链接：http://pat.zju.edu.cn/contests/pat-a-practise/1013

并查集

// 思绪太乱，没有想好就写
// 另外，所用变量名字，大小写都出现，生出不少端倪
// 图的并查集问题有些生疏
// 
// 本题思路：
// 1.去掉被占领城市所有的边，计算合并次数ans, 
// 	 则ans-1为结果（去掉连通占领城市的边）
// 2.合并时，跳过被占领的城市


#include <stdio.h>

#define SIZE 1000+10
#define INF -1

int map[SIZE][SIZE], nmap[SIZE][SIZE];
int n, m, K;
int fa[SIZE];

int getfa(int x)
{
	if(x == fa[x])
		return x;
	else
		fa[x] = getfa(fa[x]);
	return fa[x];
}

void Init()
{
	int i;
	for(i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			if(i != j)
			{
				map[i][j] = INF;
			}
			else
			{
				map[i][j] = 0;
			}	
		}
	}
	return ;
}

void Initfa()
{
	int i, j;
	for(i=1; i<=n; i++)
	{
		fa[i] = i;
	}

	for(j=1; j<=n; j++)
	{
		int k;
		for(k=j; k<=n; k++)
		{
			int a= getfa(j);
			int b= getfa(k);
			if(nmap[j][k] == 1)
			{
				fa[b] = a;
			}
		}
	}// 连通的节点合并
	return ;
}

void newMap(int city)
{
	int i, j;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
		{
			if(i == city || j == city)
			{
				nmap[i][j] = INF;	
			}
			else
			{
				nmap[i][j] = map[i][j];
			}
				
		}
	}
	return ;
}

void Printmap(int map[SIZE][SIZE])
{
	int i, j;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
		{
			printf("%2d ", map[i][j]);
		}
		printf("\n");
	}
	return ;

}


int main()
{

	#ifdef ONLINE_JUDGE
	#else
		freopen("E:\\in.txt", "r", stdin);
	//	freopen("E:\\out.txt", "w", stdout);
	#endif

	scanf("%d%d%d", &n, &m, &K);
	Init();
	int i, c1, c2;
	for(i=0; i<m ; i++)
	{
		scanf("%d%d", &c1, &c2);
		map[c1][c2] = map[c2][c1] = 1;
	}

//	Printmap(map);
	while(K-->0)
	{
		if(n <= 2)
		{
			printf("0\n");
			continue;
		}
		
		int lc;//losted city
		scanf("%d", &lc);
		newMap(lc);
		Initfa();

//		printf("\n");
//		Printmap(nmap);
		
		int ans=0, j;
		for(j=1; j<=n; j++)
		{
			if(j == lc)
			{
				continue;
			}
			int k;
			for(k=j; k<=n; k++)
			{
				if(k ==lc)
				{
					continue;
				}

				int a= getfa(j);
				int b= getfa(k);
				if(a != b)
				{
					ans++;
					fa[b] = a; 
				}
			}
		}
		printf("%d\n", ans);

	}
	return 0;
}