注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[nbut] 1246 Virtual Friends  

2012-11-01 23:12:09|  分类: NBUT OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题就是并查集,但是因为都是字符串,所以要考虑怎么储存。
有人用字典树去做,= =、我直接就用map了。

  • 问题描述
  • These days, you can do all sorts of things online. For example, you can use various websites to make virtual friends. For some people, growing their social network (their friends, their friends' friends, their friends' friends' friends, and so on), has become an addictive hobby. Just as some people collect stamps, other people collect virtual friends.

    Your task is to observe the interactions on such a website and keep track of the size of each person's network.

    Assume that every friendship is mutual. If Fred is Barney's friend, then Barney is also Fred's friend.

  • 输入
  • The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer F, the number of friendships formed, which is no more than 100 000. Each of the following F lines contains the names of two people who have just become friends, separated by a space. A name is a string of 1 to 20 letters (uppercase or lowercase).
  • 输出
  • Whenever a friendship is formed, print a line containing one integer, the number of people in the social network of the two people who have just become friends.
  • 样例输入
  • Fred Barney 
    Barney Betty 
    Betty Wilma 
  • 样例输出
  • 4



#include<iostream>
#include<map>
#include<string>
#include<string.h>
using namespace std;

map<string,int> name;
int parent[100001];
int rank[100001];

int Find(int x)
{
if (parent[x] == x) return x;
parent[x]=Find(parent[x]);
return parent[x];
}
void Union(int x, int y)
{
int xx = Find(x);
int yy = Find(y);
if(xx != yy)
{
parent[yy] = xx;
rank[xx] += rank[yy];
}
}


int main()
{
int T;
while(cin>>T)
{
while(T--)
{
memset(rank,0,sizeof(rank));
memset(parent,0,sizeof(parent));
name.clear();
int n; cin>>n;
int num = 0;
for(int i = 0;i < n;i ++)
{
char a[100];
char b[100];
scanf("%s%s",&a,&b);
string str1(a),str2(b);
if(name[str1] == NULL)
{
num ++;
name[str1] += num;
parent[name[str1]] = name[str1];
rank[name[str1]] = 1;
}
if(name[str2] == NULL)
{
num ++;
name[str2] += num;
parent[name[str2]] = name[str2];
rank[name[str2]] = 1;
}
Union(name[str1],name[str2]);
printf("%d\n",rank[Find(name[str1])]);
}

}
}

}

/*
样例输入
1
3
Fred Barney
Barney Betty
Betty Wilma
样例输出
2
3
4*/



  评论这张
 
阅读(131)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018