駐車場 [ARC 056 : B]

問題

B: 駐車場 - AtCoder Regular Contest 056 | AtCoder
N頂点、M辺の無向グラフが与えられる。
頂点1から頂点Nまで順番に以下の操作を行う

• 頂点iについて、頂点Sから頂点iまでのパスを探す
• そのパスのうち、頂点i+1から頂点Nで構成されたものがあれば、その頂点番号を出力

1 <= N, M <= 2*10^5

思考の流れ

1. N, M <= 2*10^5 ということは O(NlogN) ぐらいでは？
2. 始点は単一である

ダイクストラ感出てる。

解法

Submission #781008 - AtCoder Regular Contest 056 | AtCoder
ダイクストラっぽい感じに解く

初期化（グラフは隣接リストで持つ）

int N, M, S;
vector<int> E[201010];
 
cin >> N >> M >> S; S--;
rep(i, 0, M)
{
	int u, v; cin >> u >> v;
	u--; v--;
	E[u].push_back(v);
	E[v].push_back(u);
}

int dist[201010];
bool done[201010];
priority_queue<pair<int, int> > que;

que.push(make_pair(S, S));
dist[S] = S;

while (!que.empty())
{
	int d = que.top().first;
	int i = que.top().second;
	que.pop();
	
	if (done[i]) continue;
	done[i] = true;
	
	for (int j : E[i])
	{
		int dd = min(d, j);
		if (dist[j] < dd)
		{
			dist[j] = dd;
			que.push(make_pair(dd, j));
		}
	}
}

rep(i, 0, N) if (i <= dist[i]) printf("%d\n", i + 1);