NOJ——1274The battle of Red Cliff（并查集按秩合并）

[1274] The battle of Red Cliff
时间限制: 1000 ms　内存限制: 65535 K
问题描述
Zero loves palying Sanguo game very much, The battle of Red Cliff is one of scenes. Now he will put a fire to one of ships. Some ships are connected, some are not.Now, zero puts his fire, please tell him how many ships will be left.
输入
Input until EOF.
There are two positive integers N(2<N<100) and M(0<M<100), N means the number of ships, M means the number of command.
Then M lines follows. Each line has two positive integers x and y means he will connect these two ships by a rope.
Last line will include a number of ship's that zero will burn.
输出
The ship's number is from 1 N, every ship which is connected a burning ship will also be burned.Now, please tell zero how many ships will be left.
样例输入

样例输出
```
4

2
```

WA数次，后来换了个思路，直接求被烧掉的船所在集合的元素个数即可。答案就是总船数减掉集合元素个数。

代码：

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

using namespace std;

typedef long long LL;

#define INF 0x3f3f3f3f

#define MM(a) memset(a,0,sizeof(a))

int pos[1100];

int rank[1100];

inline int find(int x)

{

	if(x!=pos[x])

		return pos[x]=find(pos[x]);

	return pos[x];

}

inline void joint(int a,int b)

{

	int aa=find(a),bb=find(b);

	if(aa!=bb)

	{

		if(rank[aa]<rank[bb])

		{

			pos[aa]=bb;

			rank[bb]+=rank[aa];

		}

		else

		{

			pos[bb]=aa;

			rank[aa]+=rank[bb];

		}

	}

}

int main(void)

{

	int m,n,i,ans,x,y,t;

	while (~scanf("%d%d",&n,&m))

	{

		MM(pos);MM(rank);

		for (i=0; i<1100; i++)

		{

			pos[i]=i;

			rank[i]=1;

		}

		for (i=1; i<=m; i++)

		{

			scanf("%d%d",&x,&y);

			joint(x,y);

		}

		scanf("%d",&t);

		ans=0;

		t=find(t);

		printf("%d\n",n-rank[t]);

	}

	return 0;

}

巴特西

NOJ——1274The battle of Red Cliff（并查集按秩合并）

[1274] The battle of Red Cliff

最新文章

热门文章