UVA 247 - Calling Circles (Floyd)
2024-09-30 03:50:09
互相可以打电话是一个传递关系,所以Floyd求传递封包,dfs找一个尽量大的圈。
#include<bits/stdc++.h>
using namespace std; const int maxn = ;
map<string,int> mp;
map<string,int>::iterator it;
vector<string> 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()-;
}
bool vis[maxn];
int n,m; void dfs(int u)
{
vis[u] = true;
for(int i = ; 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[],s2[];
int kas = ;
while(scanf("%d%d",&n,&m),n){
if(kas) putchar('\n');
memset(d,,sizeof(d));
names.clear(); mp.clear();
while(m--) {
scanf("%s%s",s1,s2);
d[ID(s1)][ID(s2)] = true;
} for(int i = ; i < n; i++) d[i][i] = true;
for(int k = ; k < n; k++)
for(int i = ; i < n; i++)
for(int j = ; 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,);
for(int i = ; i < n; i++){
if(!vis[i]){
printf("%s",names[i].c_str());
dfs(i);
putchar('\n');
}
}
}
return ;
}
最新文章
- ZKWeb网站框架介绍
- CSS background 属性
- ssh ip ";WARING:REMOTE HOST IDENTIFICATION HAS CHANGED!";
- HDFS权限问题
- long和Long的区别
- hdu4756 Install Air Conditioning(MST + 树形DP)
- 用日志文件备份sqlserver
- 凭证(Credential)
- Windows 编程中恼人的各种字符以及字符指针类型
- 自己动手编写IOC框架(三)
- Java如何计算一个程序的运行时间
- sql注入-推断是否存在SQL注入-加法和减法
- 京东饭粒捡漏V1.0.7
- Leetcode 190.颠倒二进制位 By Python
- go学习day1
- TYPE_SCROLL_INSENSITIVE is not compatible with CONCUR_UPDATABLE
- HTTP首部字段
- linux下安装nginx,centos安装nginx
- 适配移动端的在图片上生成水波纹demo
- P1162 填涂颜色 洛谷