難問です。どのようなアルゴリズムをつくればよいか全くわかりません

[masuter]

現在、ある問題をといています。

＿問題＿
あなたはクリスマスパーティーに学校内の自分の友達と，自分の友達の友達を招待することにした． あなたの通う学校の生徒数は n 人であり，それぞれの生徒には 1 から n までの番号が割り振られている． あなたの番号は 1 である． あなたの手元には，誰と誰が友達であるかを記したリストがある． このリストをもとに， あなたがクリスマスパーティーに招待する生徒数を求めるプログラムを作成せよ．

＿入力(ファイル　リダイレクト)＿
入力の1 行目には学校の生徒数 n （2 ≦ n ≦ 500）が， 2 行目にはリストの長さ m （1 ≦ m ≦ 10000）が書かれている． 入力は全部で 2+m 行からなる．2+i 行目（1 ≦ i ≦ m）には 2 つの整数 ai と bi （1 ≦ ai ＜ bi ≦ n）が空白区切りで書かれており，番号 ai と番号 bi の生徒が友達同士であることを表す． 入力の 3 行目から 2+m 行目には同じ友達関係を表す行が重複して現れることはない

＿出力＿
出力は，あなたがクリスマスパーティーに招待する生徒数のみを含む 1 行からなる

___入出力例___

入力例1
6
5
1 2
1 3
3 4
2 3
4 5

出力例1

3

入力例2

6
5
2 3
3 4
4 5
5 6
2 5
　
出力例2
0

入力例 1 において，あなたの友達は番号 2 と番号 3 の生徒の 2 人である． また，番号 3 と番号 4 の生徒は友達同士であるので， 番号 4 の生徒はあなたの友達の友達である． 番号 5 と番号 6 の生徒はあなたの友達でもなく，あなたの友達の友達でもない． したがって，あなたは番号 2,3,4 の 3 人の生徒をクリスマスパーティーに招待する．
入力例 2 において，あなたには友達はいない． したがって，あなたがクリスマスパーティーに招待する生徒数は 0 人である

___友達から得たヒント＿＿

この問題では，ともだちのともだちの人数を求める必要がある．ここでまず，ともだちの人数を求める方法を考えてみる．
ともだちの人数を求める方法はいくつかあるが，そのなかに配列を利用した方法がある． この方法では，1番からn番の生徒を配列のそれぞれに対応させる． ともだち同士の組み合わせ全体に対して片方が1番であるかを調べて配列に招待されたかどうか印をつける． 最後に印の数を数えれば重複してカウントされることが無い．
上記の方法を拡張すると，ともだちのともだちを求めることが可能になる．
配列をもう一つ用意する．ともだち同士の組み合わせ全体に対して，先ほどの配列で印がついてる人とともだち同士の人を探す．新しい配列のその人に対応する場所に印をつける． このようにすると，ともだちのともだちである人に印がついた配列が完成する． あとは数を数えれば答えが求まる．
もちろん1番の人をカウントしないことや，ともだちの人数も忘れずにカウントする必要がある


まずはループでリストの長さだけまわして、生徒の番号を配列に格納していけばいいのでしょうか。

[みけCAT]

オフトピック

情報オリンピックの問題ですね。
無断転載、とくに出典を明示しない無断転載はよくない気がします。
JOI 2009-2010 予選 問題３
パーティー | Aizu Online Judge

[かずま]

どこが難問なんでしょうか？
すなおに解答を書くとよろしくないようなので、
難解な表現にしてみました。
理解できたら、分かりやすいプログラムに書き直して
提示してください。

コード:

#include <stdio.h>

int main(void)
{
    int n, m, i, j, k = 0, a[1000][2], b[500+1], c[500+1];
    scanf("%d%d", &n, &m);
    for (i = 0; i < m; i++) scanf("%d%d", &a[i][0], &a[i][1]),
        a[i][0]==1 && b[a[i][1]]++, a[i][1]==1 && b[a[i][0]]++;
    for (j = 2; j <= n; j++) if (b[j]) for (i = 0; i < m; i++)
        a[i][0]==j && c[a[i][1]]++, a[i][1]==j && c[a[i][0]]++;
    for (j = 2; j <= n; j++) k += (b[j] || c[j]);
    printf("%d\n", k);
    return 0;
}

アルゴリズムは、友達リストを a に読み込み、
1 の友達を b にチェックし、b の友達を c にチェックし、
b と c のチェック済みを数えているだけなんですが、
これのどこが難問なんでしょうか？

[かずま]

すみません。訂正です。
a, b, c を次のようにグローバル変数にしてください。

コード:

int a[1000][2], b[500+1], c[500+1];

int main(void)
{
    int n, m, i, j, k = 0;
   ...
}

ゼロで初期化されていないとダメなので。

[masuter]

ありがとぅございました。解決しました

[かずま]

ありがとぅございました。解決しました

どのようにして解決したのか、
および何が分からなかったのかを書いてください。

理解できたら、分かりやすいプログラムに書き直して
提示してください。

と書いたのに、そのプログラムがありません。

次のようなものを期待していました。

コード:

#include <stdio.h>
 
int a[1000][2]; // 友達リスト
int b[500+1];   // 1 の友達 (0:友達ではない, 1:友達)
int c[500+1];   // 1 の友達の友達 (0:友達ではない, 1:友達)

int main(void)
{
    int n;  // 生徒数
    int m;  // 友達リストの要素数
    int i, j;
    int k = 0;  // 1 の友達と、友達の友達の人数

    scanf("%d%d", &n, &m);
    for (i = 0; i < m; i++)    // 友達リストをすべて
        scanf("%d%d", &a[i][0], &a[i][1]);  // 読み込む

    for (i = 0; i < m; i++) {  // 友達リストを見て
        if (a[i][0] == 1)      //   1 の友達であれば
            b[a[i][1]] = 1;    //     1 の友達に印付け
        if (a[i][1] == 1)      //   1 の友達であれば
            b[a[i][0]] = 1;    //     1 の友達に印付け
    }
    for (j = 2; j <= n; j++)   // 1 を除く生徒全員について
        if (b[j])              //   j が 1 の友達であれば
            for (i = 0; i < m; i++) {  // 友達リストを見て
                if (a[i][0] == j)      //   j の友達であれば
                    c[a[i][1]] = 1;    //     j の友達に印付け
                if (a[i][1] == j)      //   j の友達であれば
                    c[a[i][0]] = 1;    //     j の友達に印付け
            }

    for (j = 2; j <= n; j++)  // 1 を除く生徒全員から
        if (b[j] || c[j]) k++;  // 友達の数を数える

    printf("%d\n", k);
    return 0;
}

アルゴリズムは、最初の質問の「友達から得たヒント」にすべて
書かれていて、それを素直にコーディングしただけです。

タイトルが
「どのようなアルゴリズムをつくればよいか全くわかりません」
となっていますが、
「どのようにコーディングすればよいか全くわかりません」
ということだったのでしょうか？