Chokudai SpeedRun 002 : K - 種類数 β

これも500ptでいいかもね。
https://atcoder.jp/contests/chokudai_S002/tasks/chokudai_S002_k

問題

N個の正整数のペア(Ai,Bi)が与えられる。
各ペアから任意の1要素を選ぶとき、選んだN個の整数のうち最大でいくつユニークなものが含まれうるか。

解法

正整数をラベルに持つ無向グラフを考える。
各ペアに対しAi-Bi間に無向辺を張ってみよう。

ペアから1要素を選ぶということは、辺の両端のいずれかの整数を選ぶということになる。
よって、n頂点の連結成分がある場合、

• 連結成分内の変数がn-1ならn-1個要素を選べる
• 連結成分内の変数がn以上ならn個要素を選べる

そこで、ここでは以下の解法を取った。

• まず登場する整数を座標圧縮する
• 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<404040> uf;

map<int,int> M;
int N;
int E[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		if(M.count(x)==0) {
			j=M.size();
			M[x]=j;
		}
		if(M.count(y)==0) {
			j=M.size();
			M[y]=j;
		}
		x=M[x];
		y=M[y];
		
		if(uf[x]==uf[y]) {
			E[uf[x]]=1;
		}
		else {
			E[uf[x]]=E[uf[y]]=E[uf[x]]|E[uf[y]];
			uf(x,y);
		}
	}
	
	int num=0;
	FOR(i,M.size()) if(uf[i]==i) {
		if(E[uf[i]]) num+=uf.count(i);
		else num+=uf.count(i)-1;
	}
	
	cout<<num<<endl;
}

まとめ

座標圧縮パートが余り面白くないので、A,Bも2N以下でもいいんじゃないかなーと思ったけども。