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行)