题目:

思路:

利用Floyd求传递闭包(mp[i][j] = mp[i][j]||(mp[i][k]&&mp[k][j]);),当mp[i][j]=1&&mp[j][i]=1的时候,i 和 j就是在同一个电话圈中。

代码:

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX 1000000000
#define FRE() freopen("in.txt","r",stdin)
#define FRO() freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
const int maxn = ;
int n,m,cnt;
map<string,int> idx;
string name1,name2;
string st[maxn];
int mp[maxn][maxn],vis[maxn]; int id(string name){
if(!idx.count(name)){
idx[name] = cnt;
st[cnt] = name;
return cnt++;
}
return idx[name];
} int main(){
//FRE();
int kase = ;
while(scanf("%d%d",&n,&m) && n){
memset(mp,,sizeof(mp));
memset(vis,,sizeof(vis));
idx.clear();
cnt=; for(int i=; i<m; i++){
cin>>name1>>name2;
int p = id(name1),q = id(name2);
mp[p][q] = ;
} for(int k=; k<n; k++){
for(int i=; i<n; i++){
for(int j=; j<n; j++){
mp[i][j] = mp[i][j]||(mp[i][k]&&mp[k][j]);
}
}
}
if(kase)cout<<endl;
cout<<"Calling circles for data set "<<++kase<<":"<<endl;
for(int i=; i<n; i++){
if(vis[i]==){
cout<<st[i];
vis[i] = ;
for(int j=i+; j<n; j++){
if(vis[j]==&&mp[i][j]&&mp[j][i]){
cout<<", "<<st[j];
vis[j]=;
}
}
cout<<endl;
}
}
}
return ;
}

最新文章

  1. ie6、7、8兼容部分css3
  2. 【字符编码】字符编码 &amp;&amp; Base64编码算法
  3. 主机和虚拟机不能ping通问题
  4. 关于absolute 和 relative 定位的定义
  5. sql float 转换为 nvarchar
  6. Servlet的一些细节问题
  7. KMP的next[]数组
  8. CSS3新特性(阴影、动画、渐变、变形、伪元素等)
  9. linux安装和配置 mysql、redis 过程中遇到的问题记录(转)
  10. ASP.NET Zero--14.一个例子(7)商品分类管理-分类搜索及分页
  11. bzoj 3894: 文理分科
  12. LeetCode之“链表”:Merge Two Sorted Lists &amp;&amp; Merge k Sorted Lists
  13. bzoj 2429: [HAOI2006]聪明的猴子 (最小生成树)
  14. Linux df du 命令
  15. 监督学习之knn算法
  16. webdriver自动化脚本
  17. string.replace替换
  18. 非IT人士的云栖酱油之行 (程序猿迷妹的云栖之行)
  19. egret学习记录
  20. 并发编程(三)------并发类容器Copy-On-Write容器

热门文章

  1. vue的学习网址
  2. 聚类-----KMeans
  3. FastDFS的介绍
  4. CodeForces 382C Arithmetic Progression (排序+分类讨论)
  5. bzoj 1232: [Usaco2008Nov]安慰奶牛cheer【最小生成树】
  6. Ajax 知识点总结
  7. Lind.DDD.DynamicModules动态模块化的设计
  8. 认识 jQuery (第一笔 点出重点)
  9. 设置Echarts鼠标悬浮样式
  10. (二)Mybatis总结之通过Dao层与数据交互