Szczegółowe omówienie zadania Cyclic Components:
Link do powyższego omówienia zadania Cyclic Components: https://youtu.be/P4xemLnkDFc?t=770
Link do treści zadania Cyclic Components i możliwości umieszczania rozwiązań:
https://codeforces.com/problemset/problem/977/E
Zadanie Cyclic Components pokazuje jak chodzić po grafie używając algorytmu DFS:
https://youtu.be/P4xemLnkDFc?t=1243
Zadanie z Codeforces! https://youtu.be/gTEmPXiN53U?t=13
Pozwala stworzyć fantastyczne CV! https://youtu.be/gTEmPXiN53U?t=5557
–
Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625
Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/
Zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php
Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109
–
Kod C++ programu Cyclic Components, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
vector<int> G[MAXN];
bool odwiedzone[MAXN];
bool dobry_cykl;
void DFS(int v)
{
odwiedzone[v] = true;
if (G[v].size() != 2)
dobry_cykl = false;
for (size_t i = 0; i < G[v].size(); ++i) {
int u = G[v][i];
if (!odwiedzone[u])
DFS(u);
}
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
int wynik = 0;
for (int i = 1; i <= n; ++i) {
if (!odwiedzone[i]) {
dobry_cykl = true;
DFS(i);
if (dobry_cykl)
++wynik;
}
}
cout << wynik << '\n';
return 0;
}
Kod C++ programu Cyclic Components, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
Kod Python programu Cyclic Components, który otrzymuje 100%:
from sys import stdin input = stdin.readline # implementacja iteracyjna def DFS(start, G, odwiedzone): dobry_cykl = True stack = [] stack.append(start) while (len(stack) > 0): v = stack.pop() odwiedzone[v] = True if (len(G[v]) != 2): dobry_cykl = False for u in G[v]: if (not odwiedzone[u]): stack.append(u) return dobry_cykl def solve(): n, m = map(int, input().split()) G = [[] for i in range(n + 1)] for i in range(m): u, v = map(int, input().split()) G[u].append(v) G[v].append(u) odwiedzone = [False] * (n + 1) wynik = 0 for i in range(1, n + 1): if (not odwiedzone[i]): if (DFS(i, G, odwiedzone)): wynik += 1 print(wynik) solve()