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.
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.
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).
Vstup:
2 7 4 1
Výstup:
1 3
Vstup:
5 11 4 2
Výstup:
1 2
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 <iostream>
#include <vector>
#include <queue>
#include <climits> // 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<long> 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<int> 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;
}