Codeforces #286 Div1 D. Mr. Kitayuta's Colorful Graph

Cよりだいぶ簡単なD。
http://codeforces.com/contest/506/problem/D

問題

1～N番のN頂点とM辺からなる無向グラフがある。
各辺は色が塗られている。

ここでQ個のクエリが与えられる。
各クエリは(A[i],B[i])からなり、A[i]番とB[i]番の頂点を１種類の色の辺だけで連結できるか、可能な辺の色の数を答えよ。

解法

クエリを先読みしておく。
色別のグラフを考え、クエリに相当する頂点対が連結するか数えていく。
その際、各色のグラフの辺の数E[i]で処理を変える。

• 辺の数が少ない場合
  • その辺をもつ頂点群についてUnion-Findで連結判定する。
  • 次に、その頂点群の対のうちクエリに含まれるものについて答えを1加算する
• 辺の数が多い場合
  • N頂点全てについてUnion-Findで連結判定する。
  • 次に、各クエリの頂点対に対して連結なら1加算する

辺の数が少ない場合はその色の辺をもつ頂点対を総当たりするので１色O(E[i]^2)、辺の数が多い場合はクエリ分の頂点対を総当たりするので１色O(Q)となる。
実際は辺の数が多いクエリ数はそれほど多くないので、O(Q)かかるパターンは少なく、時間に間に合う。

class UF {
	public:
	int um;
	vector<int> ufpar,ufrank,ufcnt;
	UF(int um_=100002) { um=um_; ufrank=vector<int>(um,0); ufcnt=vector<int>(um,1); for(int i=0;i<um;i++) ufpar.push_back(i);}
	int operator[](int x) {return (ufpar[x]==x)?(x):(ufpar[x] = operator[](ufpar[x]));}
	int count(int x) { return ufcnt[operator[](x)];}
	void unite(int x,int y) {
		x = operator[](x); y = operator[](y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int N,M,Q;
int U[101000],V[101000];
vector<pair<int,int> > E[101000];
map<int,int> R[101000];
const int D=300;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>j;
		E[j-1].push_back(make_pair(x-1,y-1));
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>U[i]>>V[i];
		R[--U[i]][--V[i]]=0;
	}
	FOR(i,M) if(E[i].size()) {
		if(E[i].size()<=D) {
			map<int,int> m;
			ITR(it,E[i]) m[it->first]=m[it->second]=0;
			x=0;
			ITR(it,m) it->second=x++;
			UF uf(x);
			ITR(it,E[i]) uf.unite(m[it->first],m[it->second]);
			ITR(it,m) ITR(it2,m) if(uf[it->second]==uf[it2->second] && R[it->first].count(it2->first)) R[it->first][it2->first]++;
		}
		else {
			UF uf(N);
			ITR(it,E[i]) uf.unite(it->first,it->second);
			FOR(j,N) ITR(it,R[j]) if(uf[j]==uf[it->first]) it->second++;
		}
	}
	FOR(i,Q) _P("%d\n",R[U[i]][V[i]]);
	
}

まとめ

CとDの難易度差がだいぶあるなぁ。