Omówienie zadania Favorite Colors / USACO Gold

Omówienie zadania Favorite Colors / USACO Gold

Szczegółowe omówienie zadania Favorite Colors z Amerykańskiej Olimpiady Informatycznej USACO, dywizji GOLD
https://youtu.be/CpHQ8PLG71E

Link do zadania Favorite Colors:
Zadanie Favorite Colors to ciekawe zadanie grafowe.
Zadanie warto zrobić gdyż pochodzi z dywizji GOLD Amerykańskiej Olimpiady Informatycznej USACO.
To poziom I/II etapu Olimpiady Informatycznej Licealistów.
I gotowy wpis do CV: https://tiny.pl/tbjvh
——-
Kod C++ programu Oceny, który jest omówiony w powyższym filmie i który otrzymuje 100%

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

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

constexpr int M=2e5+7;

vector<int>G[M];
vector<int>onecow[M];
int fau[M];
int col[M];
queue<int>Q;

void onion(int a, int b){
	if(a==b) return;

	if(onecow[a].size()+G[a].size()>onecow[b].size()+G[b].size()) swap(a,b);
	
	for(auto w:onecow[a]){
		fau[w]=b;
		onecow[b].push_back(w);
	}
	
	onecow[a].clear();
	
	for(auto w:G[a]) G[b].push_back(w);
	
	G[a].clear();
	
	if(G[b].size()>1) Q.push(b);
}

int main(){
	setIO("fcolor");
	
	int n,m,a,b,v,color=0;
	
	cin>>n>>m;
	
	for(int i=1; i<=n; i++){
		onecow[i].push_back(i);
		fau[i]=i;
	}
	
	for(int i=1; i<=m; i++){
		cin>>a>>b;
		G[a].push_back(b);
	}
	
	for(int i=1; i<=n; i++) if(G[i].size()>1) Q.push(i);
	
	while(Q.size()){
		v=Q.front();
		if(G[v].size()<2){Q.pop(); continue;}
		
		a=G[v].back();
		b=G[v][0];
		G[v].pop_back();
		onion(fau[a],fau[b]);
	}
	
	for(int i=1; i<=n; i++){
		if(!col[fau[i]]) col[fau[i]]=++color;
		cout<<col[fau[i]]<<'\n';
	}
	
	return 0;
}
Link do pliku z kodem C++ zadania Favorite Colors 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz