Cyclic components – Omówienie zadania z Codeforces – Jak chodzić po grafie? – Algorytm DFS

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()

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz