ARC079 C : Cat Snuke and a Voyage(300)

作成日:2017.07.30
最終更新日:2017.07.30

問題概要

問題本文

 $1$から$N$の番号のついた$N$個の頂点と、頂点$a_i,b_i$間を結ぶ$M$本の辺からなるグラフが与えられる。 頂点$1$と頂点$N$は直接辺で結ばれてはいない。 この時、与えられたグラフの頂点$1$と頂点$N$の距離が$2$であるか判定せよ。
制約
$3 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$1 \leq a_i < b_i \leq N$
$(a_i,b_i) \neq (1,N)$
$i \neq j$ならば$(a_i,b_i) \neq (a_j,b_j)$

考え方

 頂点$1,N$の距離が$2$である時、ある頂点$v (\neq 1,N)$が存在して頂点$1,v$間を結ぶ辺と頂点$v,N$間を結ぶ辺がともに存在する。 よって、そのような$v$が存在するかを調べれば良い。

ソースコード

マクロ等はこちら

const int MC = 200010;
int N,M;
bool x[MC] , y[MC];

bool judge(){
	repp(v,2,N){
		if(x[v] && y[v]) return 1;
	}
	return 0;
}

int main(){
	scanf("%d%d" , &N , &M);
	repp(i,0,M){
		int a,b;
		scanf("%d%d" , &a , &b);
		if(a==1) x[b] = 1;
		if(b==N) y[a] = 1;
	}
	printf("%s\n" , judge() ? "POSSIBLE" : "IMPOSSIBLE");
	return 0;
}

解法まとめ

 頂点$1,N$から辺で直接つながっている頂点をそれぞれ$x,y$に列挙する。(17,18行)
 ある頂点$v$が頂点$1,N$と辺で直接つながっているかを調べる。(5-10行)

ARC079の他の問題 D E F

自己紹介

プログラミングとか合成音声とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

最終更新日:2023.03.05

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

寄付モドキ

0冂から10000冂まで
詳しくはこちら