{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"以下の2つのネットワークを考えます。これらのネットワーク内でデータがピアツーピアの基盤で直接接続されたノード間を移動すると仮定すると、左側のネットワークの単一のノード3の障害は、まだ利用可能なノードの一部が互いに通信できなくなります。ノード1と2は引き続き互いに通信できますし、ノード4と5も同様ですが、他のノード間の通信は不可能になります。\r\u003cbr\u003e\r\u003cbr\u003eしたがって、ノード3はこのネットワークの単一障害点(SPF)です。厳密には、SPFは利用できるノードの少なくとも1組の通信を妨げるノードと定義されます。それまで完全に接続されたネットワーク上で。右側のネットワークにはそのようなノードがないことに注意してください。ネットワークにSPFはありません。利用可能なノードのペアが通信できなくなるには、少なくとも2台のマシンが故障する必要があります。\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/174c017dd19df5f4745d501731a36738?v\u003d1705063106\"\u003e\u003c/center\u003e"}},{"title":"入力","value":{"format":"HTML","content":"入力には複数のネットワークの説明が含まれます。ネットワークの説明は、接続されたノードを識別する整数のペアで構成されます。1行に1組のペアがあり、ペアの順序は関係ありません。1 2と2 1は同じ接続を指定します。すべてのノード番号は1から1000までの範囲になります。単一のゼロが含まれる行が接続されたノードのリストの終わりを示します。空のネットワークの説明は入力の終わりを示します。入力ファイルの空行は無視する必要があります。"}},{"title":"出力","value":{"format":"HTML","content":"入力された各ネットワークについて、ファイル内の番号を出力し、存在するSPFノードのリストを続けます。\r\u003cbr\u003e\r\u003cbr\u003eファイル内の最初のネットワークは「Network#1」として識別され、2番目は「Network#2」などとします。各SPFノードについて、以下の例に示すように、ノードとそのノードの障害時に残る完全に接続されたサブネットの数を識別する行を出力します。ネットワークにSPFノードがない場合は、SPFノードのリストの代わりに「SPFノードなし」というテキストを出力します。"}},{"title":"サンプル","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 2\r\n5 4\r\n3 1\r\n3 2\r\n3 4\r\n3 5\r\n0\r\n\r\n1 2\r\n2 3\r\n3 4\r\n4 5\r\n5 1\r\n0\r\n\r\n1 2\r\n2 3\r\n3 4\r\n4 6\r\n6 3\r\n2 5\r\n5 1\r\n0\r\n\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNetwork #1\r\n SPF node 3 leaves 2 subnets\r\n\r\nNetwork #2\r\n No SPF nodes\r\n\r\nNetwork #3\r\n SPF node 2 leaves 2 subnets\r\n SPF node 3 leaves 2 subnets\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}