博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVA 247 - Calling Circles (Floyd)
阅读量:6799 次
发布时间:2019-06-26

本文共 1455 字,大约阅读时间需要 4 分钟。

互相可以打电话是一个传递关系,所以Floyd求传递封包,dfs找一个尽量大的圈。

#include
using namespace std;const int maxn = 25;map
mp;map
::iterator it;vector
names;bool d[maxn][maxn];int ID(const string& s){ if((it = mp.find(s))!=mp.end()) return it->second; mp.insert(make_pair(s,names.size())); names.push_back(s); return names.size()-1;}bool vis[maxn];int n,m;void dfs(int u){ vis[u] = true; for(int i = 0; i < n; i++){ if(!vis[i] && d[u][i] && d[i][u]){ printf(", %s",names[i].c_str()); dfs(i); } }}int main(){ //freopen("in.txt","r",stdin); char s1[50],s2[50]; int kas = 0; while(scanf("%d%d",&n,&m),n){ if(kas) putchar('\n'); memset(d,0,sizeof(d)); names.clear(); mp.clear(); while(m--) { scanf("%s%s",s1,s2); d[ID(s1)][ID(s2)] = true; } for(int i = 0; i < n; i++) d[i][i] = true; for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){ d[i][j] |= d[i][k]&&d[k][j]; } printf("Calling circles for data set %d:\n",++kas); fill(vis,vis+n,0); for(int i = 0; i < n; i++){ if(!vis[i]){ printf("%s",names[i].c_str()); dfs(i); putchar('\n'); } } } return 0;}

 

转载于:https://www.cnblogs.com/jerryRey/p/4758393.html

你可能感兴趣的文章
[Leetcode] Container With Most Water
查看>>
查看版本信息的命令
查看>>
Linux搭建SVN服务器
查看>>
UML 之 数据流图(DFD)
查看>>
IO知识点整理(文件File类的使用)
查看>>
mahout 实现canopy
查看>>
修炼你自己
查看>>
窥探一句话木马后门的背后
查看>>
Kafka设计解析(二):Kafka High Availability (上)-转
查看>>
bzoj2186【SDOI2008】沙拉公主的困惑
查看>>
Lambda 表达式的演示样例-来源(MSDN)
查看>>
什么场景应该用 MongoDB ?
查看>>
python学习:猜数字游戏
查看>>
Linux 进程、线程运行在指定CPU核上
查看>>
iOS11开发教程(二十三)iOS11应用视图实现按钮的响应(3)
查看>>
微软自然语言理解平台LUIS:从零开始,帮你开发智能音箱
查看>>
Centos创建用户
查看>>
视频列表
查看>>
python2 和 python3 区别
查看>>
cd4与cd8比值的意义
查看>>