UVA 247 Calling Circles (그림 에 패키지 전달)

문제 풀이:
만약 에 두 사람 이 서로 전화 (직접 또는 간접) 를 하면 그들 은 같은 전화 권 에 있다 고 말한다. 예 를 들 어 a 는 b, b 는 c, c 는 d, d 는 a 에 게 전 화 를 하면 이 네 사람 은 같은 권 에 있다. 만약 에 e 가 f 에 게 전 화 를 하지만 f 가 e 에 게 전 화 를 하지 않 으 면 e 와 f 는 같은 전화 권 에 있 지 않 고 n (25 이하) 사람의 m 번 전 화 를 입력 하여 모든 전화 권 을 찾 아 낸다.
floyd 로 전달 폐쇄, 즉 d [i] [j] 를 구하 면 i 가 직접 또는 간접 적 으로 j 에 게 전 화 를 걸 었 는 지 여 부 를 나타 내 고 d [i] [j] = 1 과 d [j] [i] = 1 일 때 두 사람 은 같은 전화 권 에 있 고 dfs 출력 을 합 니 다.
코드

#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <ctime>
#include <cmath>
#include <cctype>
using namespace std;
#define MAX 100000
#define LL long long
int cas=1,T;
int n,m;
vector<string> name;
const int INF = 1000000;
int d[105][105];
int vis[30];

int change(string s)
{
    for (int i = 0;i<name.size();i++)
    {
        if (name[i]==s)
            return i;
    }
    name.push_back(s);
    return name.size()-1;
}
void dfs(int i)
{
    vis[i]=1;
   for (int j = 0;j<n;j++)
   {
       if (!vis[j] && d[i][j]==1 && d[j][i]==1)
       {
           cout << ", " << name[j];
           dfs(j);
       }
   }
}

int main()
{
    while (scanf("%d%d",&n,&m) &&n)
    {
        name.clear();
        memset(d,0,sizeof(d));
        for (int i = 0;i<n;i++)
        {
            d[i][i]=1;
        }
        for (int i = 0;i<m;i++){
        string s1,s2;
        cin >> s1 >> s2;
        d[change(s1)][change(s2)]=1;
        }

        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][j] || (d[i][k] && d[k][j]);
        if (cas>1)
            printf("
");
        printf("Calling circles for data set %d:
",cas++);
        memset(vis,0,sizeof(vis));
        for (int i = 0;i<n;i++)
        {
           if (!vis[i])
           {
               cout << name[i];
               dfs(i);
               printf("
"); 
           }
        }
    }
    //freopen("in","r",stdin);
    //scanf("%d",&T);
    //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}

제목.
If you’ve seen television commercials for long-distance phone companies lately, you’ve noticed that many companies have been spending a lot of money trying to convince people that they provide the best service at the lowest cost. One company has “calling circles.” You provide a list of people that you call most frequently. If you call someone in your calling circle (who is also a customer of the same company), you get bigger discounts than if you call outside your circle. Another company points out that you only get the big discounts for people in your calling circle, and if you change who you call most frequently, it’s up to you to add them to your calling circle. LibertyBell Phone Co. is a new company that thinks they have the calling plan that can put other companies out of business. LibertyBell has calling circles, but they figure out your calling circle for you. This is how it works. LibertyBell keeps track of all phone calls. In addition to yourself, your calling circle consists of all people whom you call and who call you, either directly or indirectly. For example, if Ben calls Alexander, Alexander calls Dolly, and Dolly calls Ben, they are all within the same circle. If Dolly also calls Benedict and Benedict calls Dolly, then Benedict is in the same calling circle as Dolly, Ben, and Alexander. Finally, if Alexander calls Aaron but Aaron doesn’t call Alexander, Ben, Dolly, or Benedict, then Aaron is not in the circle. You’ve been hired by LibertyBell to write the program to determine calling circles given a log of phone calls between people. 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