Gildie – Omówienie zadania z I etapu Olimpiady Informatycznej

Gildie – Omówienie zadania z I etapu Olimpiady Informatycznej

Link do treści zadania Gildie:
https://szkopul.edu.pl/problemset/problem/ptF7RsWMiiMdzzZWt5BKFAnT/site

Szczegółowe omówienie zadania Gildie – I etap Olimpiady Informatycznej Licealistów:

Link do powyższego omówienia zadania Gildie:
https://youtu.be/3J-Pe-w-oFc?t=1929
Zadanie Gildie pochodzi z I etapu XVII Olimpiady Informatycznej:
https://szkopul.edu.pl/task_archive/oi/

Zadanie Gildie wymaga zastosowania algorytmu DFS chodzenia po grafie
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
———

#include<bits/stdc++.h>
using namespace std;

constexpr int M=2e5+7;

vector<int>g[M];
int k[M];

void nie(){
	cout<<"NIE\n";
	exit(0);
}

void dfs(int v){
	for(auto w:g[v]){
		if(k[w]!=-1) continue;
		k[w]=k[v]^1;
		dfs(w);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m,a,b;
	cin>>n>>m;
	
	for(int i=1; i<=n; i++) k[i]=-1;
	
	for(int i=1; i<=m; i++){
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	for(int i=1; i<=n; i++){
		if(g[i].empty()) nie();
		if(k[i]!=-1) continue;
		k[i]=0;
		dfs(i);
	}
	
	cout<<"TAK\n";
	for(int i=1; i<=n; i++) cout << ( k[i] ? "K\n" : "S\n" );
	
	return 0;
}
Kod C++ zadania Gildie, który jest omówiony w powyższym filmie i który otrzymuje 100% 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz