问题分析

$Erdos$数问题本质是图论中的最短路径问题。每个科学家为图的节点，共同发表论文的关系构成无向边，$Erdos$数定义为从"$Erdos, P.$"到目标节点的最短路径长度。由于边无权值，适合用广度优先搜索（$BFS$）求解最短路径。

核心思路

图模型构建

• 将每位作者视为节点，同一篇论文的所有作者间建立无向边（即合作关系）。
• 例如，若论文作者为$A、B、Erdos$，则$A$与$B$、$A$与$Erdos$、$B$与$Erdos$之间均有边。

BFS遍历计算Erdos数

• 从"$Erdos, P.$"节点出发进行$BFS$，首次访问某节点时的层数即为其$Erdos$数：
  • 直接与Erdos合作过的作者（距离$1$）→ $Erdos$数为$1$；
  • 与$Erdos$数$1$的作者合作过但未直接与$Erdos$合作的作者（距离$2$）→ $Erdos$数为$2$，以此类推。
• 无法通过路径到达的节点，$Erdos$数为无穷大。

c++实现

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 10010
const int inf = 0x7fffffff; 
map<string, int> table;
vector<int> G[MAX];
int d[MAX];
bool inq[MAX];
int P, N;
void build_graph() {
    table.clear();
    for (int i = 0; i < MAX; ++i) {
        G[i].clear();
    }
    int cnt = 0;
    string buffer;
    vector<int> g;
    while (P--) {
        g.clear();
        getline(cin, buffer);
        string name = "";
        int len = (int)buffer.length() - 1;
        
        while (buffer[len] != ':') --len;
        
        int k = 0;
        for (int i = 0; i < len; ++i) {
            if (buffer[i] == ',') ++k;
            if (k != 2) {
                name += buffer[i];
            } else {
                k = 0;
                if (table.find(name) == table.end()) {
                    table[name] = cnt++;
                    g.push_back(cnt - 1);
                } else {
                    g.push_back(table[name]);
                }
                name = "";
                ++i;
            }
        }
        
        if (table.find(name) == table.end()) {
            g.push_back(cnt);
            table[name] = cnt++;
        } else {
            g.push_back(table[name]);
        }
        
        for (size_t i = 0; i < g.size(); ++i) {
            for (size_t j = 0; j < g.size(); ++j) {
                if (g[i] != g[j]) {
                    G[g[i]].push_back(g[j]);
                }
            }
        }
    }
}
void bfs() {
    for (int i = 0; i < MAX; ++i) {
        d[i] = inf;
        inq[i] = false;
    }
    if (table.find("Erdos, P.") == table.end()) {
        while (N--) {
            string name;
            getline(cin, name);
            cout << name << ": infinity" << endl;
        }
        printf("\n");
        return;
    }
    int s = table["Erdos, P."];
    d[s] = 0;
    queue<int> q;
    q.push(s);
    inq[s] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (size_t i = 0; i < G[x].size(); ++i) {
            int y = G[x][i];
            if (d[y] > d[x] + 1) {
                d[y] = d[x] + 1;
                if (!inq[y]) {
                    q.push(y);
                    inq[y] = true;
                }
            }
        }
    }
    
    while (N--) {
        string name;
        getline(cin, name);
        cout << name << ": ";
        if (table.find(name) == table.end() || d[table[name]] == inf) {
            cout << "infinity" << endl;
        } else {
            cout << d[table[name]] << endl;
        }
    }
    printf("\n");
}
int main() {
    int cas = 0;
    while (scanf("%d%d", &P, &N) == 2) {
        if (N == 0 && P == 0) break;
        ++cas;
        printf("Database #%d\n", cas);
        cin.ignore(); 
        build_graph();
        bfs();
    }
    return 0;
}