Codeforces #544: Div3. F2. Spanning Tree with One Fixed Degree

中盤のミスが多すぎた回。
https://codeforces.com/contest/1133/problem/F2

問題

連結無向グラフと、整数Dが与えられる。
このグラフの全域木のうち、頂点1の次数がDとなるものがあるか。
あるなら一例を答えよ。

解法

まず、頂点1の辺のうち、全域木に必須な辺を求めよう。
頂点１を除いた辺で森をつくる。
ここで全域木を作るために頂点１からの辺がいくつか必要ならば、それは必須の辺とする。

改めて全域木を作る。
まず必須の辺を全域木に入れた後、頂点１を端点とする辺をD本まで追加する。
あとは、頂点１が絡まない辺を使い全域木を作る。

int N,M,D;
vector<int> E[202020];
int used[202020];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<202020> uf;
vector<pair<int,int>> R;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>D;
	FOR(i,M) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	int ma=0;
	
	for(i=2;i<=N;i++) {
		FORR(e,E[i]) if(uf[e]!=uf[i] && e!=1 && i!=1) {
			uf(e,i);
		}
	}
	
	int num=0;
	for(i=2;i<=N;i++) if(uf[i]==i) num++;
	if(D<num || D>E[1].size()) return _P("NO\n");
	
	FORR(e,E[1]) if(uf[e]!=uf[1]) {
		uf(e,1);
		used[e]=1;
		D--;
	}
	
	
	FORR(e,E[1]) if(D&&used[e]==0) {
		used[e]=1;
		D--;
	}
	
	uf.reinit();
	FORR(e,E[1]) if(used[e]==1) {
		uf(e,1);
		R.push_back({1,e});
	}
	
	for(i=2;i<=N;i++) FORR(e,E[i]) if(e!=1 && uf[i]!=uf[e]) {
		uf(e,i);
		R.push_back({i,e});
	}
	
	
	
	
	cout<<"YES"<<endl;
	FORR(r,R) cout<<r.first<<" "<<r.second<<endl;
	
	
}

まとめ

Div3としてちょうど良い加減のひねり具合だと思う。