Tävlingsprogrammering/Uppgifter/Erdös-nummer

Erdös-nummer

Matematikern Paul Erdös är bl.a. känd för att vara den matematiker som skrivit flest matematiska publikationer (Leonhard Euler har dock flest skrivna sidor). Erdös samarbetade väldigt mycket i sina publikationer. Ociterade källor hävdar att han ofta var temporärt inneboende hos en kollega. Under besöken skrev han en publikation tillsammans med kollegan och när gästfriheten tog slut flyttade Erdös vidare till nästa kollega.

Det innebär stor prestige att ha skrivit en publikation med Erdös. De som har skrivit en publikation med Erdös definieras ha Erdös-nummer 1. Ifall man skrivit en publikation med en person med Erdös-nummer 1 så får man Erdös-nummer 2 o.s.v.

Givet en lista över publikationer, skriv ut en lista med alla inblandade matematikers Erdös-nummer.

Indata

Först raden innehåller två heltal, 1 ≤ N ≤ 5000 och 1 ≤ M ≤ 40000, antalet matematiker respektive antalet publikationer. Därefter följer M rader. Varje rad börjar med ett heltal, antalet matematiker som samarbetade i publikationen. Sedan följer matematikernas namn (mellanslags-separerade), ordningen på matematikerna spelar ingen roll. Matematikernas namn består av 1 till 20 stora bokstäver, 'A' - 'Z'. Inga olika matematiker har samma namn. Erdös heter ERDOS. I varje publikation kommer det vara minst 2 och högst 5 matematiker. Du kan anta att Erdös-numret är ändligt för alla inblandade matematiker.

Utdata

En nyrads-separerad lista med matematiker och deras Erdös-nummer. ERDOS ska vara med i denna lista, hans Erdös-nummer är alltid 0. Listan ska vara sorterad i alfabetisk ordning.

Exempel 1: Indata 5 4

2 ERDOS IMMERMAN
2 JACKSON IMMERMAN
3 ERDOS JACKSON IMMERMAN
3 BACH JACKSON RUBINSTEIN

Exempel 1: Utdata

BACH 2
ERDOS 0
IMMERMAN 1
JACKSON 1
RUBINSTEIN 2

Exempel 2: Indata

10 10
2 ERDOS JYVZ
2 QHD DNJMFFHIVNTXOR
2 GXNVNYPG ERDOS
2 JYVZ DNJMFFHIVNTXOR
3 RIZTHDDFLKTKHLUMS GXNVNYPG AOFJAZXUBICBIIPP
2 LFX GXNVNYPG
2 GOGDYHYXDRHCKQHQV AOFJAZXUBICBIIPP
2 AOFJAZXUBICBIIPP QHD
3 NWLMBD AOFJAZXUBICBIIPP QHD
2 DNJMFFHIVNTXOR NWLMBD

Exempel 2: Utdata

AOFJAZXUBICBIIPP 2
DNJMFFHIVNTXOR 2
ERDOS 0
GOGDYHYXDRHCKQHQV 3
GXNVNYPG 1
JYVZ 1
LFX 2
NWLMBD 3
QHD 3
RIZTHDDFLKTKHLUMS 2

Lösning

Skulle vi ha id-nummer på folk istället för namn skulle det bli lite lättare att hantera uppgiften. Nu är vi tvungna att skapa någon sorts tabell med alla namn som mappar på någonting. en std::map<string, int> kan vara bra att använda för att kolla vilket id-nummer ett visst namn tillhör. När vi lägger till ett namn ser den automatiskt till att man inte lägger till samma namn två gånger.

Hur som helst, uppgiften kan ses som en vanlig enkel "kortaste vägen"-uppgift där alla bågar är lika långa (1) och varje nod är en person. Vi vill ta reda på kortaste vägen från Erdös till alla andra personer. Lösningen på det problemet heter BFS, bredden-först-sökning. Vi börjar på Erdös, ser vilka personer han ansluter till. Dessa har Erdös-nummer 1. När vi gjort det kollar vi alla som hade Erdös-nummer 1 och ser vilka de i sin tur ansluter till. Dessa kommer få Erdös-nummer 2. Och så vidare. Om vi träffar på någon som redan hade ett tidigare Erdös-nummer är det klart att vi inte ändrar det till ett högre värde. Enklaste datastrukturen för att hålla koll på vilka vi ska besöka är en kö (queue). Personer att besöka läggs till längst bak i kön. Nästa person att gå igenom hämtas från längst fram av kön. På så sätt är vi säkra på att vi alltid besöker alla med Erdös-nummer 1 först, sedan de med nummer 2, sedan nr 3 osv. Det är bra att ha en tabell på vilka Erdös-nummer folk fick. Den initialiseras till t.ex. -1 eller INF.

Lösning av Andreas Wallström i C++11:

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <utility>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); // Snabbar upp cin till scanf() nivåer

    int N, M, P, counter = 0, INF = -1;
    string name;
    map<string, int> names; // Vi ger alla namn ett ID...
    map<int, string> ids;   // ...och alla IDn har ett namn

    cin >> N >> M;
    vector<vector<int>> adjacencyList(N, vector<int>());
    while(M--) {
       vector<string> tmpnames;

        // Läs in alla namn
        cin >> P;
        while(P--) {
            cin >> name;
            tmpnames.push_back(name);

            // Ge varje namn ett unikt ID
            if(names.find(name) == names.end()) {
                ids[counter] = name;
                names[name]  = counter;
                counter++;
            }
        }

        // Bygg upp adjacency listan
        for(string name1 : tmpnames)
            for(string name2 : tmpnames)
                adjacencyList[names[name1]].push_back(names[name2]);
    }

    
    queue<int> theQueue;
    theQueue.push(names["ERDOS"]); // Vi vill veta avståndet från ERDOS
    vector<int> dist(N, INF);
    dist[names["ERDOS"]] = 0; // Avståndet från ERDOS till ERDOS är 0

    //BFS
    while(!theQueue.empty()) {
        int parentVertex = theQueue.front();
        theQueue.pop();

        for(int vertex : adjacencyList[parentVertex]) {
            if(dist[vertex] == INF) { // Har ej besökt denna vertex (person) förut
                theQueue.push(vertex);
                dist[vertex] = dist[parentVertex] + 1; // Avståndet till denna person är = förra personens avstånd till ERDOS + 1.
            }
        }
    }

    // Bygg ihop resultatet till önskat format
    vector<pair<string, int>> result;
    for(int i = 0; i < dist.size(); ++i)
        result.push_back(make_pair(ids[i], dist[i])); // [(namn, avstånd), ...]

    sort(result.begin(), result.end()); // Sortera på namn

    for(auto x : result) {
        cout << x.first << " " << x.second << endl; // Skriv ut resultatet
    }
}