#include #include // 28-Z2-6 Kalamita // Jenda Hadrva // Asymptotická časová složitost: O(N * K) // // (Na reálném počítači nás trochu zbytečně brzdí spojové seznamy. Jednotlivé // prvky jsou totiž náhodně rozmístěné po paměti. Pokud bychom je měli hezky // popořadě v poli, budeme k nim mít díky cache procesoru rychlejší přístup.) // Struktura pro jeden prvek spojového seznamu struct spojovy_seznam { int vrchol; // Pořadové číslo vrcholu struct spojovy_seznam *dalsi; // Ukazatel na další prvek seznamu }; int main(void) { int n, k; scanf("%d %d", &n, &k); // Alokace paměti // Funkce calloc navíc zaručuje, že je paměť vynulovaná struct spojovy_seznam **P = calloc(n, sizeof(struct spojovy_seznam *)); // Každou hranu máme ve dvou spojových seznamech, proto potřebujeme 2k prvků // Nechceme alokovat paměť pro každý prvek seznamu zvlášť struct spojovy_seznam *spoj = malloc(2 * k * sizeof(struct spojovy_seznam)); for (int i = 0; i < k; i++) { int a, b; scanf("%d %d", &a, &b); // Vložení na začátek spojáku spoj[2*i].vrchol = b; spoj[2*i].dalsi = P[a]; P[a] = &spoj[2*i]; spoj[2*i + 1].vrchol = a; spoj[2*i + 1].dalsi = P[b]; P[b] = &spoj[2*i + 1]; } int trojuhelniku = 0; char *matice = calloc(n, sizeof(char)); // Jeden řádek matice sousednosti for (int a = 0; a < n; a++) { // Proměnnou a iterujeme přes číslo vrcholu for (struct spojovy_seznam *b = P[a]; b; b = b->dalsi) { // b je pouze ukazatel na prvek spojového seznamu // Samotnou hodnotu vrcholu najdeme v b->vrchol matice[b->vrchol] = 1; } for (struct spojovy_seznam *b = P[a]; b; b = b->dalsi) { if (a < b->vrchol) { // Zaručíme podmínku a < b for (struct spojovy_seznam *c = P[b->vrchol]; c; c = c->dalsi) { // Překontrolujeme, že c je soused a: if (matice[c->vrchol] && (b->vrchol < c->vrchol)) trojuhelniku++; // Pouze pokud a < b < c } } } for (struct spojovy_seznam *b = P[a]; b; b = b->dalsi) { matice[b->vrchol] = 0; } } printf("%i\n", trojuhelniku); // Každý trojúhelník máme jen jednou, nedělíme 6 // Uvolnění paměti free(matice); free(spoj); free(P); return 0; }