Problem Description 如果两个人相互打电话（直接或间接），则说他们在同一个电话圈里。例如,a打给b，b打给c，c打给d，d打给a，则这四 个人在同一个圈里；如果e打给f但f不打给e，则不能推出e和f在同一个电话圈里。输入n(n<=25)个人的m次电话，找出所 有电话圈。人名只包含字母，不超过25个字符，且不重复。
Input The input file will contain one or more data sets. Each data set begins with a line containing two integers, n and m. The first integer, n, represents the number of different people who are in the data set. The maximum value for n is 25. The remainder of the data set consists of m lines, each representing a phone call. Each call is represented by two names, separated by a single space. Names are first names only (unique within a data set), are case sensitive, and consist of only alphabetic characters; no name is longer than 25 letters. For example, if Ben called Dolly, it would be represented in the data file as Ben Dolly Input is terminated by values of zero (0) for n and m.
Output For each input set, print a header line with the data set number, followed by a line for each calling circle in that data set. Each calling circle line contains the names of all the people in any order within the circle, separated by comma-space (a comma followed by a space). Output sets are separated by blank lines.
Sample Input 5 6 Ben Alexander Alexander Dolly Dolly Ben Dolly Benedict Benedict Dolly Alexander Aaron 14 34 John Aaron Aaron Benedict Betsy John Betsy Ringo Ringo Dolly Benedict Paul John Betsy John Aaron Benedict George Dolly Ringo Paul Martha George Ben Alexander George Betsy Ringo Alexander Stephen Martha Stephen Benedict Alexander Stephen Paul Betsy Ringo Quincy Martha Ben Patrick Betsy Ringo Patrick Stephen Paul Alexander Patrick Ben Stephen Quincy Ringo Betsy Betsy Benedict Betsy Benedict Betsy Benedict Betsy Benedict Betsy Benedict Betsy Benedict Quincy Martha 0 0
Sample Output Calling circles for data set 1: Ben, Alexander, Dolly, Benedict Aaron Calling circles for data set 2: John, Betsy, Ringo, Dolly Aaron Benedict Paul, George, Martha, Ben, Alexander, Stephen, Quincy, Patrick
参考AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<map>
#include<vector>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
int vis[30],f[30][30];
map<string,int>name;
vector<string>Name;
int flag=1;
int n,m;
void dfs(int u)
{
vis[u]=1;
for(int i=0;i<n;i++)
if(f[u][i]&&f[i][u])
if(!vis[i])
{
cout<<", "<<Name[i];
dfs(i);
}
}
int main()
{
while(cin>>n>>m)
{
if(n==0&&m==0)
break;
name.clear();
Name.clear();
memset(f,0,sizeof(f));
memset(vis,0,sizeof(vis));
int id=0;
for(int i=0;i<m;i++)
{
string a,b;
cin>>a>>b;
if(!name.count(a))
{
name[a]=id++;
Name.push_back(a);
}
if(!name.count(b))
{
name[b]=id++;
Name.push_back(b);
}
int x=name[a],y=name[b];
f[x][y]=1;
}
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
f[i][j]=(f[i][j]||(f[i][k]&&f[k][j]));
if(flag>1)
cout<<endl;
cout<<"Calling circles for data set " << flag++ <<":" << endl;
Problem Description 输入一个C个点S条边（c<=100,s<=1000）的无向带权图，边权表示该路径上的噪声值。当噪声值太大时，耳膜可能会受到 伤害，所以当你从某点去往另一个点时，总是希望路上经过的最大噪声值最小。输入一些询问，每次询问两个点，输出两 点间最大噪声值最小的路径。
Input The input may contain multiple test cases. The first line of each test case contains three integers C(≤ 100), S(≤ 1000) and Q(≤ 10000) where C indicates the number of crossings (crossings are numbered using distinct integers ranging from 1 to C), S represents the number of streets and Q is the number of queries. Each of the next S lines contains three integers: c1, c2 and d indicating that the average sound intensity level on the street connecting the crossings c1 and c2 (c1 ̸= c2) is d decibels. Each of the next Q lines contains two integers c1 and c2 (c1 ̸= c2) asking for the minimum sound intensity level you must be able to tolerate in order to get from crossing c1 to crossing c2. The input will terminate with three zeros form C, S and Q.
Output For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then for each query in the input print a line giving the minimum sound intensity level (in decibels) you must be able to tolerate in order to get from the first to the second crossing in the query. If there exists no path between them just print the line “no path”. Print a blank line between two consecutive test cases.
