1．问题描述
给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输？
2．基本要求
（1）输入要求：输入若干测试数据组成。对于每一组测试，第1行包含一个整数N（≤10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。接下来的几行输入格式为I C1 C2或者 C或者C C1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。
当N为0时，表示全部测试结束，不要对该数据做任何处理。
（2）输出要求：对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。
当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“The network is connected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。
两组测试数据之间请输出一空行分隔。
测试数据：
3
C 1 2
I 1 2
C 1 2
S
3
I 3 1
I 2 3
C 1 2
S
0
输出：
no
yes
There are 2 components

yes
The network is connected
程序：
#include <iostream>
using namespace std;
#define N 507
static int arcs[N+1][N+1];
static int m;
static bool g=false;
void connect(int a,int b)
{
for(int k=a;k<m+1;k++)
{
if(arcs[a][k]==1 && k!=b)
{
if(arcs[k][b]==1)
    {
cout<<"yes"<<endl;
g=true;
break;
}
else connect(k,b);
}
}//for
}
int main()
{
int a,b;
int count;
char x;
    cin>>m;
while(m!=0)
{
for(int i=1;i<N+1;i++)
{
for(int j=1;j<N+1;j++)
arcs[i][j]=0;
}
g=false;
count=m;
cin>>x>>a>>b;
while(x=='I')
{
arcs[a][b]=1;
arcs[b][a]=1;
cin>>x>>a>>b;
}
while(x=='C')
{
 if(arcs[a][b]==1)
 {
cout<<"yes"<<endl;
    g=true;
break;
 }//if
 else
 connect(a,b);
if(!g)
cout<<"no"<<endl;
          cin>>x;
}//while
if(x=='S')
{
for(int i=1;i<m;i++)
{
for(int j=i+1;j<m+1;j++)
{
if(arcs[i][j]==1)
{
count--;
    break;
}//if
}//for
}//for
if(count==1)
cout<<"The network is connected."<<endl;
else
cout<<"There are "<<count<<" componets."<<endl;
cin>>m;
}//if
}//while
while(m==0)
{
exit(0);
}
return 0;
}




[ 本帖最后由 SHENHUNTIAN 于 2011-1-5 10:51 编辑 ]