質問です。

[きお]

C言語のことについての質問です。
1,2,3,という駅があるとします。
数字を2つ入力して、例えば1と2を入力して、「1と2を繋げました」と出力します。
次に2と3を入力して、「2と3を繋げました」と出力します。

そして、1と3を入力したときに、前の状態で1と3は2を通じて繋がっています。なので「1と3は繋がっている」と出力させたいのですが、このプログラムの組み方が分かりません。文字の入力、出力方法は分かっています。1、2、3の繋がりのところが分かりません。もしよろしかったら駅の数を増やした状態も教えていただけるとありがたいです。

できればプログラムのソースを・・・

[softya（ソフト屋)]

知恵袋に非常に似た質問有るのですが、同じ方ですか？

「C言語のことについての質問です。 1,2,3,という駅があるとします。 数字を2つ入力... - Yahoo!知恵袋」
http://detail.chiebukuro.yahoo.co.jp/qa ... 1260676307

[きお]

同じ人です。。

できれば多く早く情報を得たかったので。

申し訳ないです。

[softya（ソフト屋)]

こちらでは、直接ソースコードを提示するより考え方とかアルゴリズムとかでアドバイスしています。
ソースコードを提示してもらえば、ソース自体のアドバイスも出来ます。
詳しくは、フォーラムルールを御覧ください。
http://dixq.net/board/board.html

[xxx]

入力された数がグループになっているかどうかを判定する。という風に読み替えてみるとunion-findというデータ構造を使うだけで済みます
http://algorithms.blog55.fc2.com/blog-entry-46.html
http://www.prefield.com/algorithm/conta ... _find.html
ここらを参考にするといいと思います。

【追記】
C言語という条件を見逃していました。
簡単に書いたのでこちらも参考にしてみてください
グループの判定をより高速にするためにグループのリーダーを使うようにしています。

コード:

#define MAX 3
int p[MAX];
/* union-findの初期化 */
void union_init(void)
{
  int i;
  for(i=0;i<MAX;i++){
    p[i] = i; /* グループが自分のみの状態にする */
  }
}
/* aのリーダーを返す */
int root(int a)
{
  /* グループのリーダーの場合 */
  if(p[a] == a) return a; /* リーダーの番号を返す */
  return p[a]=root(p[a]); /* どこのグループに属しているか分かれば十分なのでリーダーを書き換える */
}
/* aとbが同じグループか */
int same(int a,int b)
{
  return root(a)==root(b);
}
/* aとbを同じグループにする */
void merge(int a,int b)
{
  /* aのリーダーをbのリーダーにする */
  p[root(a)]=root(b);
}

[softya（ソフト屋)]

入力された数がグループになっているかどうかを判定する。という風に読み替えてみるとunion-findというデータ構造を使うだけで済みます
http://algorithms.blog55.fc2.com/blog-entry-46.html
http://www.prefield.com/algorithm/conta ... _find.html
ここらを参考にするといいと思います。

それ実装がC++だと思いますよ。

>>きおさん。

自分の今出来る範囲でプログラムを組んでもらうとアドバイスしやすいです。
あと知恵袋のjjacksspanさんのアルゴリズムは実は問題があります。
1-2と3-4が接続していると入力するだけで、1-4は接続していると見なされてれてしまいます。

問題自体にも不明点があって、
・最大駅は幾つまでなのか？mallocを使って良いのか？
・路線は１つだけなのか？それとも山手線と中央線の関係のように複数の路線を想定するのか？