AtCoder ABC #126 : E - 1 or 2

500pt以上になったので久々にABC。
https://atcoder.jp/contests/abc126/tasks/abc126_e

問題

N個の変数があり、その値は1か2である。
ここで、ある2つの変数の和の偶奇に関する情報が与えられる。

この状態で、最小で何個の値がわかれば全部の値を辿れるか。

解法

情報がある2変数について、片方がわかればもう片方が確定する。
よって、変数を頂点とみなし、情報を2変数を結ぶ辺とみなしたとき、各連結成分に対し1個変数の値がわかれば連結成分内の全変数の値が確定する。

ここまでわかると、あとは連結成分をUnion-Findで数えるだけ。

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<101010> uf;
int N,M;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		uf(x,y);
	}
	int ret=0;
	for(i=1;i<=N;i++) if(i==uf[i]) ret++;
	cout<<ret<<endl;
}

まとめ

ページ開くの重くなってきたの残念。