読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.244 ★1のグラフの問題

問題はこちら
No.244 ★1のグラフの問題 - yukicoder

辺を動いて行き来できる頂点集合を島と呼ぶことにする
問題は「N頂点を1つの島にするには最低何本の辺が必要か?」
2つの島があった時、それぞれの島に属する頂点を1つずつ選び、その2頂点間を辺で結ぶと島が1つになる、つまり全体の島の数が1つ減る。
また辺を1つ増やすことで減らせる島の数は高々1つ(その辺の両端が属していた島以外には影響がないので)
これより、最初の時点ではN頂点全てが孤立していて島はN個あることから、N-1本が答え

int main(){
	int n;
	scanf("%d",&n);
	printf("%d",n-1);
	return 0;
}

迷うところはないでしょう

n;main(){n=!printf("%d",atoi(gets(&n))-1);}

43B