Je to tu – obdobie extrémnej nákupovej mánie. Zľavy na zľavy, čierne piatky, kybernetické pondelky, mikulášske akcie… Škoda len, že sa nám tento rok minuli aj rozprávky k zadaniam, vypredali sa dokonca ešte rýchlejšie ako RAMky v zľave. Budete si teda musieť vystačiť len s holou úlohou:
Máme zadaný neorientovaný graf $G$, kde každý vrchol má stupeň1 najviac $d \leq 16$. Klika v grafe je taká podmnožina vrcholov, v ktorej je každá dvojica vrcholov spojená. Nájdite počet klík veľkosti $k$ v grafe $G$. Dve kliky počítame ako rôzne ak sa líšia v aspoň jednom vrchole.
V prvom riadku vstupu sú čísla $n, m, k$ udávajúce počet vrcholov grafu $G$, počet hrán grafu $G$, a veľkosť klík, ktoré chceme hľadať.
Nasleduje $m$ riadkov, na každom sú dve čísla $a_i, b_i$ ($0 \leq a_i, b_i < n$) popisujúce hrany grafu. Je garantované, že graf neobsahuje slučky a násobné hrany.
Označme $d$ maximálny stupeň vrchola v grafe $G$. V jednotlivých sadách platia nasledujúce obmedzenia:
| Sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $1 \leq n,k \leq$ | $30$ | $5\,000$ | $5\,000$ | $5\,000$ |
| $0 \leq d \leq$ | $10$ | $10$ | $14$ | $16$ |
Vypíšte jeden riadok a v ňom jedno číslo udávajúce počet klík veľkosti presne $k$, ktoré sa nachádzajú v grafe.
4 5 3
0 1
1 2
2 0
0 3
1 3
2
Graf obsahuje dve kliky veľkosti tri. Tie sú zložené z vrcholov {0, 1, 2} a {0, 1, 3}.
4 4 4
0 1
1 2
2 3
3 0
0
Graf neobsahuje žiadnu kliku veľkosti 4, lebo neobsahuje hrany (0, 2) a (1, 3).
Stupeň vrchola je počet hrán, ktoré z neho vychádzajú. ↩
Aby sme každú kliku započítali len raz, tak kliky budeme počítať podľa najmenších vrcholov, ktoré sú v nich. Týmto vrcholom budeme hovoriť koreň kliky. Toto vieme jednoducho docieliť tak, že si zorientujeme každú hranu, aby išla z menšieho vrchola do väčšieho. Keď sa v tomto novom grafe pozeráme na susedov nejakého vrchola $u$, tak dostaneme len tie vrcholy, ktoré môžu byť v klike s koreňom $u$.
Teraz môžeme využiť to, že každý vrchol má malý stupeň. Pre každý vrchol $u$ spočítame, koľko existuje klík s daným vrcholom ako koreňom. Na to si vygenerujeme všetky podmnožiny susedov vrchola $u$ s veľkosťou $k - 1$ (v zorientovanom grafe) a skontrolujeme, či táto $k$-tica tvorí kliku.
Označme si $d$ ako maximálny stupeň vrchola v grafe. Pre každý vrchol musíme skontrolovať najviac $d \choose k-1$ kandidátov na kliku. V závislosti od implemntácie jedna kontrola zaberie medzi $\mathcal{O}(k d)$ a $\mathcal{O}(k)$ času. Celková časová zložitosť je teda pri šikovnej implementácií kontrolovania klík $\mathcal{O}(n {d \choose k-1} k)$ . Pamäťová zložitosť je $\mathcal{O}(n + m)$. Nižšie prezentujeme riešenie so zložitosťou na kontrolu $\mathcal{O}(k d)$, k lepšej časovej zloźitosti sa dá dostať použitím podobných myšlienok ako v ďalšom riešení.
import sys
from itertools import combinations
# Skontroluje, ci vrcholy tvoria kliku
# Casova zlozitost O(k), ale hash-set je pomaly
def is_clique(vertices, adj):
n = len(vertices)
for i in range(n):
for j in range(i):
a = vertices[i]
b = vertices[j]
if a > b:
a, b = b, a
if b not in adj[a]:
return False
return True
def main():
n, m, k = map(int, input().split())
adj = [[] for _ in range(n)]
hash_adj = [set() for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
if a > b:
a, b = b, a
adj[a].append(b)
hash_adj[a].add(b)
ans = 0
for i in range(n):
neighbors = adj[i]
deg = len(neighbors)
# Ak je stupen prilis maly, netreba sa na tento vrchol pozerat
if deg < k - 1:
continue
# Vyberieme si podmnozinu k - 1 susedov vrchola i
for subset in combinations(neighbors, k - 1):
candidates = (i,) + subset
# Skontrolujeme, ci tato k-tica tvori kliku
if is_clique(candidates, hash_adj):
ans += 1
print(ans)
if __name__ == "__main__":
main()
Doteraz sme prišli na to, že počet klík veľkosti $k$ zakorenených v $u$ je rovnaký, ako počet klík veľkosti $k-1$ medzi susedmi $u$. Túto myšlienku ale môžeme ďalej zopakovať. Vyberieme si nejakého suseda $v$ vrchola $u$ ako koreň kliky veľkosti $k-1$ a v prieniku susedov vrcholov $u$ a $v$ hľadáme kliku veľkosti $k-2$. Keď sa dostaneme do momentu, že hľadáme kliky veľkosti $1$, tak je odpoveď jednoduchá, stačí vrátiť počet vrcholov v prieniku. Naopak ak nám zostáva príliš málo kandidátov na dokončenie kliky, nemusíme ďalej pokračovať. Keďže každá klika má jednoznačne určený najmenší vrchol a susedov vyberáme v zorientovanom grafe, tak každú kliku navštívime práve raz.
Aby sme tento postup vedeli efektívne implementovať, tak si potrebujeme
udržiavať množinu všetkých prípustných vrcholov a vedieť rýchlo robiť jej
prienik so susedmi nejakých vrcholov. Na to využijeme techniku tzv.
bitmasiek, teda fakt, že čísla v počítači sú reprezentované binárne. Množinu
teda vieme reprezentovať ako nejaké binárne číslo a prienik dvoch množín je len
binárny and týchto množín.
Budeme si ale musieť prečíslovať vrcholy, aby reprezentácia množiny mala málo bitov. Keďže pri hľadaní kliky zakorenenej vo vrchole $u$ sa pozeráme len na susedov vrchola $u$, tak si vrcholy prečíslujeme podľa poradia, v akom sú v zozname susedov vrchola $u$. Teda pre každý koreň $u$ a suseda $v$ si spočítame masku, ktorá hovorí, ktorých susedov majú $u$ a $v$ spoločných. Toto predpočítanie vieme spraviť napríklad v čase $\mathcal{O}(nd^3)$.
V našom rekurzívnom algorime pri prehľadávaní z vrchola $u$ postupne pridávame vrcholy kliky a “zužujeme” ďalších kandidátov na prienik so susedmi už pridaných vrcholov. Keďže sa pozeráme na susedov v zorientovanom grafe, tak ich pridávame v rastúcom poradí. To znamená, že každú kliku zakorenenú v $u$ navštívime práve raz.
Pre každú kliku veľkosti $j$ zakorenenú v $u$ teda máme jeden stav prehľadávania. Týchto stavov je pre dané $u$ najviac $d \choose j-1$. Keďže pre jednu kliku robíme len $\mathcal{O}(1)$ práce (vďaka bitmaskám), tak celková časová zložitosť bude počet klík, ktoré navštívime, teda počet stavov. Ako je popísané vyššie, stačía nám stavy len pre $j \in \{1, \ldots, k-1\}$. Celková časová zložitosť prehľadávania je teda $\mathcal{O}(n \sum_{j=0}^{k-2} {d \choose j})$.
Výsledná časová zložitosť je teda $\mathcal{O}(nd^3 + n \sum_{j=0}^{k-2}{d \choose j})$. Ak $k-1 \leq d/2$, tak binomické koeficienty budú rásť s $j$, teda ich môžeme ohraničiť najväčším koeficientom. Potom dostaneme zložitosť $\mathcal{O}(nd^3 + n {d \choose k-2} k)$. Pamäťová zložitosť je $\mathcal{O}(n + m + nd^2)$. Časová zložitosť je síce podobná ako pri šikovnej implementácií predošlého riešenia (kde kontrolu robíme pomocou bitmasiek), ale v praxi bude toto riešenie oveľa rýchlejšie. Po prvé, pomer $d \choose k-1$ a $d \choose k-2$ pre malé $k$ je približne $d/k$, teda rekurzívne riešenie je v tomto prípade asymptoticky $d/k$-krát rýchlejšie. Prípad $k-1 = d/2$ je dokonca ten “najzložitejší”, lebo v tomto prípade môže graf obsahovať najviac klík veľkosti $k$. Vtedy sú ale obe kombinačné čísla približne rovnaké, teda asymptotická časová zložitosť oboch riešení je rovnaká. Po druhé, rekurzívne riešenie navštívi len toľko klík, koľko naozaj musí. Naopak, naše prvé riešenie vyskúša všetky podmnožiny susedov daného vrchola.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using mask_t = uint16_t;
using adj_mask_t = array<mask_t, MAX_D>;
constexpr size_t MAX_D = 16;
vector<vector<int>> adj;
vector<adj_mask_t> rooted_adj_mask;
// Pocet klik zakorenenych vo vrchole root s k vrcholmi navyse.
ll count_rooted_cliques(int root, mask_t mask, int k) {
// root: koren klik, ktore hladame
// mask: vrcholy, ktore mozme pridat
// k: kolko vrcholov este treba pridat
// Ak staci pridat jeden vrchol, mozeme pridat kazdeho kandidata
if (k == 1) {
return popcount(mask);
}
// 0 vrcholov vieme pridat 1 sposobom
if (k == 0) {
return 1;
}
// Ak nemame dost kandidatov, netreba pokracovat
if (popcount(mask) < k) {
return 0;
}
ll ans = 0;
auto m = mask;
// Iterujeme cez vsetkych kandidatov a skusime rozsirit kliku
while (m > 0) {
// Najdeme index najmensieho kandidata a odstranime ho z mnoziny
auto ind = countr_zero(m);
m ^= 1<<ind;
// Novych kandidatov ziskame tak, ze pretneme aktualnych kandidatov a
// susedov pridavaneho vrchola
auto nv_mask = mask & rooted_adj_mask[root][ind];
ans += count_rooted_cliques(root, nv_mask, k-1);
}
return ans;
}
bool contains(auto vec, auto a) {
using std::ranges::find;
return find(vec, a) != vec.end();
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, m, k; cin >> n >> m >> k;
adj.resize(n);
rooted_adj_mask.resize(n);
// Spocitame zorientovany zoznam susedov, hrany orientujeme od mensieho k
// vacsiemu vrcholu
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
if (a > b) swap(a, b);
adj[a].push_back(b);
}
vector<mask_t> masks(n);
// Spocitame zakorenene masky susednosti
// rooted_adj_mask[root][i] obsahuje susedov root, ktory su aj susedia
// i-teho suseda vrcholu root
for (int i = 0; i < n;i ++) {
for (int j = 0; j < adj[i].size(); j++) {
auto cj = adj[i][j];
mask_t mask = 0;
for (int k = 0; k < adj[i].size(); k++) {
auto ck = adj[i][k];
if (contains(adj[cj], ck)) {
mask |= 1<<k;
}
}
rooted_adj_mask[i][j] = mask;
}
}
ll ans = 0;
// Spocitame pocet klik zakorenenych v kazdom vrchole
for (int i = 0; i < n; i++) {
auto deg = adj[i].size();
auto mask = (1<<deg) - 1;
ans += count_rooted_cliques(i, mask, k - 1);
}
cout << ans << '\n';
}
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete