====== Průměr grafu ====== Zadání: http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=prumergrafu Na vstupu je dán prostý neorientovaný graf bez smyček, je třeba určit počet jeho komponent a velikost průměru komponenty s největším průměrem. Průměr grafu, pokud je souvislý, je roven vzdálenosti mezi dvěma navzájem nejvzdálenějšími uzly v grafu (takových uzlů může být případně v grafu více). Vzdálenost mezi dvěma uzly je délka nejkratší cesty mezi nimi, přičemž délka cesty je rovna počtu hran v cestě. Uvažujeme graf s alespoň dvěma uzly. ===== Vstup ===== Na vstupu jsou čtyři kladná celá čísla N1, N2, D a HD zapsaná na jednom řádku a oddělená navzájem vždy jednou mezerou. Vrcholy grafu jsou všechna přirozená čísla z množiny {N1, N1+1, N1+2, ..., N2}. Hrany grafu jsou konstruovány takto: Každý uzel reprezentujeme jako binární číslo zapsané pomocí přesně D znaků 0/1. Pokud je číslo dostatečně malé, jeho zápis obsahuje příslušný počet úvodních nul. Dva uzly jsou spojeny hranou, pokud Hammingova vzdálenost těchto jejich zápisů je menší nebo nejvýše rovna HD. Hodnota D je nejvýše 62, hodnota N2 je nejvýše 2D−1, hodnota N1 je vždy alespoň o 2 a nejvýše o 5000 menší než N2. Hodnota HD se pohybuje v rozmezí od 1 do 5. ===== Výstup ===== Na výstupu jsou dvě čísla v jednom řádku oddělená mezerou. První určuje počet komponent zadaného grafu, druhé určuje maximální průměr ze všech komponent grafu (pokud je graf souvislý, je druhým číslem průměr celého grafu). ===== Příklad 1 ===== Vstup: 2 7 4 1 Výstup: 1 3 ===== Příklad 2 ===== Vstup: 5 11 4 2 Výstup: 1 2 ===== Riešenie v C++ (10/10) ===== Trik spočíva v hľadaní priemeru grafu pomocou BFS tak, že najprv spustím BFS od ľubovoľného uzla (napr. koreň) a nájdem najvzdialenejší uzol. Potom spustím BFS znovu od tohto uzla a nájdem najvzdialenejší od neho. Táto druhá vzdialenosť je hľadaný priemer grafu. Tento postup treba opakovať pre každú komponentu grafu (v prípade, že je nesúvislý). Keď už som si s tým dal zbytočnú námahu na skúške (neuspel), tak sem dávam kód, snáď to niekomu pomôže. // (Skuska 18.1.2012) A4M33PAL, Jakub Boksansky #include #include #include #include // definovany LONG_MAX using namespace std; // ------------------------------------------------------------------------- // GLOBALNE PREMENNE // ------------------------------------------------------------------------- bool* visited; long componentNumber, maxDistance; long** adjMatrix; long N1, N2, D, HD, nodeCount; // ------------------------------------------------------------------------- // POMOCNE FUNKCIE // ------------------------------------------------------------------------- // tato metoda naplni maticu susednosti hranami podla zadaneho vstupu void fillAdjMatrix(long** adjMatrix, long N1, long N2, long D, long HD, long nodeCount) { // generujem vsetky kombinacie cisel od N1 do N2 for (long i = 0; i < nodeCount; i++) { for (long j = i+1; j < nodeCount; j++) { // spocitam XOR tychto cisel - jednicky potom znamenaju rozdielnu // hodnotu na danej pozicii long xorred = (i+N1) ^ (j+N1); int hammingDistance = 0; // spocitam jednicky na prvych D poziciach tak, ze ich postupne // posuvam doprava a pocitam jednicky na poslednej pozicii (ich // pocet je rovny hammingovej vzdialenosti) for (int k = 0; k < D; k++) { hammingDistance += (xorred & 1); xorred = xorred >> 1; } // hranu musim zapisat v oboch smeroch (graf je neorientovany), // inak bude mat DFS/BFS problem if (hammingDistance <= HD) { adjMatrix[i][j] = 1; adjMatrix[j][i] = 1; } } } } // standardny rekurzivny DFS void DFS_WALK(long u) { visited[u] = true; for (long v = 0; v < nodeCount; v++) { if (adjMatrix[u][v]) { if (!visited[v]) { DFS_WALK(v); } } } } // BFS prechod grafu na najdenie priemeru. Zacne v startNode, do furthestNode // ulozi uzol, ktory je najvzdialenejsi a vrati jeho vzdialenost. Pracuje v // 2 krokoch: // 1. krok - zacne v startNode (lubovolne zvoleny) a najde uzol, ktory je // od neho najvzdialenejsi. jeho index ulozi do furthestNode // 2. krok - zacne vo furthestNode, ktory nasiel v 1. kroku a hlada // najvzdialenejsi od neho. Jeho vzdialenost vrati ako priemer gr. // Premenna firstStep urcuje, ktory krok bude vykonavat. Prvy krok automaticky // vola druhy krok. long getDistance(long startNode, long &furthestNode, bool firstStep) { queue to_visit; // pole vzdialenosti, pre kazdy uzol potrebujem jeho najmensiu // vzdialenost od pociatocneho uzla long* distances = new long[nodeCount]; long maxDistance = 0; for (long i = 0; i < nodeCount; i++) { visited[i] = false; distances[i] = LONG_MAX; } distances[startNode] = 0; to_visit.push(startNode); while(!to_visit.empty()) { long v = to_visit.front(); to_visit.pop(); if (!visited[v]) { visited[v] = true; for (long i = 0; i < nodeCount; i++) { // ak sa do uzla i da dostat nejakou hranou, a zaroven // je to kratsia cesta nez doteraz najdena ... if (adjMatrix[v][i] && distances[i] > distances[v]) { distances[i] = distances[v] + 1; if (distances[i] > maxDistance) { maxDistance = distances[i]; furthestNode = i; } to_visit.push(i); } } } } delete[] distances; // ak sme v prvom kroku vypoctu, tak rekurzivne spustime vypocet // od najvzdialenejsieho uzla, ktory sme nasli if (firstStep) { return getDistance(furthestNode, furthestNode, false); } // v druhom kroku vratime najdeny priemer grafu return maxDistance; } // ------------------------------------------------------------------------- // MAIN // ------------------------------------------------------------------------- int main( int argc, const char* argv[] ) { // ------------------------------------------------------------------------- // nacitanie vstupu // ------------------------------------------------------------------------- cin >> N1 >> N2 >> D >> HD; nodeCount = N2-N1+1; // alokujem maticu susednosti adjMatrix = new long*[nodeCount]; for (long i = 0; i < nodeCount; i++) { adjMatrix[i] = new long[nodeCount]; for (long j = 0; j < nodeCount; j++) { adjMatrix[i][j] = 0; } } // zavolame metodu na naplnenie matice susednosti hranami podla zadania fillAdjMatrix(adjMatrix, N1, N2, D, HD, nodeCount); // ------------------------------------------------------------------------- // vypocet poctu komponent (DFS) // ------------------------------------------------------------------------- // budeme potrebovat korene jednotlivych komponent (v pripade, ze graf // bude nesuvisly) vector roots; visited = new bool[nodeCount]; for (long i = 0; i < nodeCount; i++) { visited[i] = false; } componentNumber = 0; // rekurzivny DFS na najdenie poctu komponent a ich rootov for (long i = 0; i < nodeCount; i++) { if (!visited[i]) { componentNumber++; // zapamatam si roota tejto komponenty roots.push_back(i); DFS_WALK(i); } } // ------------------------------------------------------------------------- // vypocet premeru grafu // ------------------------------------------------------------------------- // temp premenna na zasobniku long furthest; // spustim BFS od vsetkych rootov na najdenie priemeru grafu for (long i = 0; i < roots.size(); i++) { //zapamatam si najvyssiu hodnotu (spomedzi priemerov vsetkych komponent) maxDistance = max(maxDistance, getDistance(roots[i], furthest, true)); } // ------------------------------------------------------------------------- // vypis vysledkov // ------------------------------------------------------------------------- cout << componentNumber << " " << maxDistance; return 0; } ~~DISCUSSION~~