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