Shaking Your Cellphone（并查集 + STL）

C - Shaking Your Cellphone

Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:65535KB     64bit IO Format:%lld & %llu

Submit Status Practice UESTC 1700

Description

Do you know a software called "WeiXin", a kind of chatting tool? There is an application called "Shaking for a while". Once you shake your cellphone, you can find those who shake their cellphone at same time.
One day when Tom was shaking his cellphone, he thought about a problem: how large the friends group would be if everyone made friends once they find others who shake cellphone at same time and combine their friends group?
We assume all the people are lonely and have no friends at the beginning. In other word, their friends group only contains themselves.

Input

First line contains an integer T (0 < T <= 10), indicate there are T cases.
For each case, the first line contains an integer N (0 < N <= 1000), indicate the number of people who would shake their cellphone.
Then follows N lines. Every line comes with an integer K[i] (0 <= K[i] <= 1440), indicate the i-th person shakes cellphone K times a day. Then follows K[i] strings shown as "HH:MM", indicate the time the i-th person shakes cellphone.

Output

For each test case, the first line contains an integer X indicate how many friends group amount the people; the second line comes X integers in nondescending order, indicate the scale of each friends group.

Sample Input

1
4
3 00:00 00:01 00:02
2 00:01 00:03
1 00:03
1 00:04

Sample Output

2
1 3 

    题意：

    有T（0到10）个case，每个case包含N（0到1000）人。然后给出每个人摇手机的时间，每个人开始有一个K（一到1440），说明摇了K次，给出每次的时间点。在所有人中，在相同时间点摇的人属于同一朋友圈的人。输入所有数据后，输出总共的朋友圈数，再按非降序顺序输出每个朋友圈的人数。

  

    思路：

    输入的时间段是字符串，拆开的话感觉不好处理，所以干脆就整体来处理，用map关联容器对这个时间点和第一次在这个时间点摇动手机的人进行配对，以后再出现有相同的时间，那么就先判断这个人与第一个在这个时间摇动手机的人是否根节点相同，如果相同则不用合并，不相同则合并起来，合并的时候用num数组来登记该根节点下的数量。

    最后循环一次，找出root[i]==i的节点（该结点为根节点），将num数量（num数量是这个朋友圈的总数）移到head数组中，同时用k登记总共有几个朋友圈，对head进行排序。最后输出k和循环输出head数组即为所求。

 

    AC：

#include<cstdio>
#include<map>
#include<string>
#include<algorithm>
#define max 1000+5
using namespace std;
int root[max],num[max],head[max];

int find(int a)
{
	if(root[a]==a) return a;
	int r=find(root[a]);
	root[a]=r;
	return r;
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		map<string,int> m;
		m.clear();
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		  root[i]=i,num[i]=1,head[i]=0;
		for(int i=1;i<=n;i++)
		{
			int ti;
			scanf("%d",&ti);
			while(ti--)
			{
			  char time[10];
			  scanf("%s",time);
			  if(m.find(time)!=m.end())
//如果这个时间段有出现过
			  	{
			  		int a,b;
			  		a=find(i);
			  		b=find(m[time]);
			  		if(a!=b)
			  		{
			  		root[a]=b;
			  		num[b]+=num[a];
			  		}
				}
			  else m[time]=i;
//没有出现过则登记这个人
			}
		}
		int k=0;
		for(int i=1;i<max;i++)
		 if(root[i]==i)  head[k++]=num[i];
		sort(head,head+k);
		printf("%d\n",k);
		for(int i=0;i<k;i++)
		  {
		  	printf("%d",head[i]);
		  	i==k-1?printf("\n"):printf(" ");
		  }
	}
	return 0;
}

 

   总结：

   WA了一次是忘了写条件if(a!=b)的时候，就是当根节点不相同的时候才合并，才根节点数量增加。如果不加条件，就是无论根节点相不相同都合并，虽然不会影响合并结果，但是会影响num数量，等于加多了一次，如果以后还有相同的，则会越加越多。细心。