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