AtCoder ARC #108 : C - Keep Graph Connected

うーんいまいち。
https://atcoder.jp/contests/arc108/tasks/arc108_c

問題

N頂点M辺の連結グラフが与えられる。
各辺には1～Nの値が設定されている。

各頂点に重複可で1～Nの値を振ったとする。
この時、各辺について、辺の値と両端の頂点の値の片方だけが等しいものを残すとする。
その後、グラフが連結であるようにしたい。
各頂点への値の割り振り例を求めよ。

解法

まず全域木を求める。
あとは、この全域木の各辺が残るように値を割り振ろう。

DFS順で値を検討していく。
もし親方向の辺と親頂点の値が一致していたら、自身は別の値にし、そうでなければ辺の値に合わせよう。

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;
	}
};


int N,M;
vector<pair<int,int>> E[202020];
UF<202020> uf;

int R[202020];

void dfs(int cur,int pre) {
	R[cur]=1;
	FORR(e,E[cur]) if(e.first==pre) {
		if(R[pre]!=e.second) {
			R[cur]=e.second;
		}
		else {
			R[cur]=e.second-1;
			if(R[cur]==0) R[cur]=2;
		}
	}
	FORR(e,E[cur]) if(e.first!=pre) dfs(e.first,cur);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		if(uf[x]!=uf[y]) {
			uf(x,y);
			E[x].push_back({y,r});
			E[y].push_back({x,r});
		}
	}
	
	dfs(1,-1);
	FOR(i,N) cout<<R[i+1]<<endl;
	
}

まとめ

意外に手間取った。