网站开发所以浏览器兼容模式,网站设计开发方案,镇江外贸型网站建设,建一个网站的步骤题意
给定两个人相互打电话#xff0c;如果a打给b,b打给c,c打给a#xff0c;则说a,b,c在同一电话圈中。给出n个人的m次通话#xff0c;输出所有的电话圈
思路
用graph[u][v]1表示u和v之间有打电话。在使用floyd算法计算所有的点对之间的值。graph[u][v]1表示u,v之间有直接…题意
给定两个人相互打电话如果a打给b,b打给c,c打给a则说a,b,c在同一电话圈中。给出n个人的m次通话输出所有的电话圈
思路
用graph[u][v]1表示u和v之间有打电话。在使用floyd算法计算所有的点对之间的值。graph[u][v]1表示u,v之间有直接或者间接打电话。如果graph[u][v] 1并且graph[v][u]1说明u和v是在同一个电话圈
代码如下
#include bits/stdc.husing namespace std;const int N 30;#define _for(i, a, b) for(int i (a); i (b); i)
#define _rep(i, a, b) for (int i (a); i (b); i)int n, m;
int graph[N][N];
bool vis[N];
mapstring, int nameMap;
vectorstring names;int getId(const string name)
{if (!nameMap.count(name)){int size names.size();nameMap[name] size;names.push_back(name);}return nameMap[name];
}void fastio()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
}int main()
{fastio();#ifndef ONLINE_JUDGEifstream fin(f:\\OJ\\uva_in.txt);streambuf* back cin.rdbuf(fin.rdbuf());#endifint kase 1;while (cin n m) {if (n 0 m 0) {break;}if (kase 1) {cout endl;}nameMap.clear();names.clear();memset(graph, 0, sizeof(graph));fill(vis, vis N, false);_for(i, 0, m) {string a, b;cin a b;int u getId(a);int v getId(b);graph[u][v] 1;}_for(k, 0, n) {_for(i, 0, n) {_for(j, 0, n) {graph[i][j] graph[i][j] || (graph[i][k] graph[k][j]);}}}cout Calling circles for data set kase : endl;_for(u, 0, n) {if (vis[u]) {continue;}vis[u] true;cout names[u];_for(v, 0, n) {if (!vis[v] graph[u][v] graph[v][u]) {vis[v] true;cout , names[v];}}cout endl;}kase;}#ifndef ONLINE_JUDGEcin.rdbuf(back);#endifreturn 0;
}
