Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

In our increasingly interconnected world, it has been speculated that everyone on Earth is related to everyone else by no more than six degrees of separation. In this problem, you must write a program to find the maximum degree of separation for a network of people.

For any two people, the degree of separation is the minimum number of relationships that must be traversed to connect the two people. For a network, the maximum degree of separation is the largest degree of separation between any two people in the network. If there is a pair of people in the network who are not connected by a chain of relationships, the network is disconnected.

As shown below, a network can be described as a set of symmetric relationships each of which connects two people. A line represents a relationship between two people. Network A illustrates a network with 2 as the maximum degree of separation. Network B is disconnected.

Input 

The input consists of data sets that describe networks of people. For each data set, the first line has two integers: P (2P50), the number of people in the network, and R (R1), the number of network relationships. Following that first line are R relationships. Each relationship consists of two strings that are names of people in the network who are related. Names are unique and contain no blank spaces. Because a person may be related to more than one other person, a name may appear multiple times in a data set.

The final test case is followed by a line containing two zeroes.

Output 

For each network, display the network number followed by the maximum degree of separation. If the network is disconnected, display `DISCONNECTED'. Display a blank line after the output for each network. Use the format illustrated in the sample output.

Sample Input 

4  4 
Ashok  Kiyoshi   Ursala  Chun   Ursala  Kiyoshi 
Kiyoshi  Chun 
4  2 
Ashok  Chun   Ursala  Kiyoshi 
6 5 
Bubba  Cooter   Ashok  Kiyoshi   Ursala  Chun 
Ursala  Kiyoshi   Kiyoshi  Chun 
0  0

Sample Output 

Network 1: 2 

Network 2: DISCONNECTED 

Network 3: DISCONNECTED

Claimer: The data used in this problem is unofficial data prepared by Derek Kisman. So any mistake here does not imply mistake in the offcial judge data. Only Derek Kisman is responsible for the mistakes. Report mistakes to dkisman@acm.org

---

all pairs 全局最短路的最大值。

#include <stdio.h>
#include <iostream>
#include <map>
#define oo 0xffff
using namespace std;

int main() {
    int n, m, cases = 0, i, j, k;
    char a[50], b[50];
    while(scanf("%d %d", &n, &m) == 2) {
        if(n == 0 && m == 0)
            break;
        int g[51][51], x, y;
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= n; j++)
                g[i][j] = oo;
            g[i][i] = 0;
        }
        map<string, int> R;
        map<string, int>::iterator it;
        int size = 0;
        while(m--) {
            scanf("%s %s", a, b);
            it = R.find(a);
            if(it == R.end())
                R[a] = ++size, x = size;
            else    x = it->second;
            it = R.find(b);
            if(it == R.end())
                R[b] = ++size, y = size;
            else    y = it->second;
            g[x][y] = g[y][x] = 1;
        }
        for(k = 1; k <= n; k++) {
            for(i = 1; i <= n; i++) {
                for(j = 1; j <= n; j++) {
                    if(g[i][j] > g[i][k] + g[k][j])
                        g[i][j] = g[i][k] + g[k][j];
                }
            }
        }
        int mx = 0;
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                if(g[i][j] > mx)
                    mx = g[i][j];
        printf("Network %d: ", ++cases);
        if(mx == oo)
            puts("DISCONNECTED");
        else
            printf("%d\n", mx);
        puts("");
    }
    return 0;
}