Szczegółowe omówienie zadania Favorite Colors z Amerykańskiej Olimpiady Informatycznej USACO, dywizji GOLD
–
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;
}