みんなのプロコン本選 : E - 瞬間移動装置

yukicoderで近い問題を見たかと思ったけど解き方は違った。
http://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_e

問題

N頂点の完全グラフから、M辺を取り除いたものが与えられる。
クエリとして２頂点対(c,d)が与えられるので、最短経路長を求めよ。

解法

Nが小さければ、毎回最短経路を求めても大した問題ではない。
逆にNが大きい場合、元の完全グラフの辺の数に対しMが小さくなるので、結果的にグラフは密になる。

よって以下のように解こう。

• (c,d)の辺が取り除かれていない
  • これは明らかに経路長は1である
• (c,d)の辺が取り除かれている
  • cとdから取り除いた辺の総和がN-2未満である
    • このとき、c-e-dとつながるようなeが1個以上あるので、経路長は2である。
  • cとdから取り除いた辺の総和が(N-2)以上である
    • 少なくともc,dの片方は取り除かれた辺が(N-2)/2以上である。

もともと密なグラフなので、そのように取り除かれた辺が多い頂点は多くなく、O(M/N)程度である。
よってそのような頂点に対しては、その点から全頂点への最短経路長を求めてしまおう。

愚直に探索すると密なグラフなのでTLEするが、逆にほぼ完全グラフであることを用いると高速化できる。
ダイクストラの要領で訪問済み頂点の隣接点をたどる点は同じである。
ただ、通常ダイクストラでは訪問済み頂点側からその隣接店を探索するが、逆に未訪問の頂点から、その訪問済み頂点に辺が残っているかを判断すると高速に処理できる。
(未訪問の頂点から訪問済み頂点に辺がのぞかれているケースは少ない)

処理の手順にもよるが、1回の探索でO((N+M)logN)程度で終わる。
全探索対象の頂点がO(M/N)程度なことを考えると、全体でO(N√NlogN)程度となる。

int N,M,Q;
vector<int> E[101010];
set<pair<int,int>> S;

int id[101010];
vector<vector<int>> Ds;
vector<int> D;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x].push_back(y);
		E[y].push_back(x);
		S.insert({x,y});
	}
	FOR(i,N) sort(ALL(E[i]));
	
	x = 0;
	FOR(i,N) {
		if(E[i].size()<N/2-2) {
			id[i]=-1;
		}
		else {
			id[i]=x++;
			D = vector<int>(N,-1);
			vector<int> left;
			FOR(j,N) if(i!=j) left.push_back(j);
			D[i]=0;
			queue<int> Q;
			Q.push(i);
			while(Q.size()) {
				y = Q.front();
				Q.pop();
				
				vector<int> left2;
				int u=0,v=0;
				while(u<left.size()) {
					if(v<E[y].size() && left[u]==E[y][v]) {
						left2.push_back(E[y][v]);
						u++, v++;
					}
					else if(v==E[y].size() || left[u]<E[y][v]) {
						D[left[u]]=D[y]+1;
						Q.push(left[u]);
						u++;
					}
					else {
						v++;
					}
				}
				swap(left,left2);
			}
			
			Ds.push_back(D);
		}
	}
	
	while(Q--) {
		cin>>x>>y;
		x--,y--;
		if(S.count({x,y})==0) {
			cout<<1<<endl;
		}
		else if(E[x].size()+E[y].size()<N-2) {
			cout<<2<<endl;
		}
		else {
			if(E[x].size()<E[y].size()) swap(x,y);
			cout<<Ds	[id[x]][y]<<endl;
		}
	}
	
}

まとめ

ほぼ完全グラフなグラフの最短経路探索テクは他にも使えそう。