如何用并查集编写网络检查（用c语言），我的有些错误 - 数据结构与算法

已结贴√ 问题点数：20 回复次数：8

如何用并查集编写网络检查（用c语言），我的有些错误

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 编辑 ]

搜索更多相关主题的帖子: 计算机　网络　正整数　如何　

第 2 楼

得分:10

顶

第 3 楼

得分:0

写了个简单的

程序代码：

#include <stdio.h>

#define NODE 10001//定义最大计算机台数为10001 零下标不采用

int Graph[NODE][NODE] = {0};//定义图的结构为邻接矩阵
bool traverse[NODE] = {0};//标志数组 表示图上的结点是否访问过
int vex_num;//顶点数

void init_traverse();//初始化标志数组
void init_Graph();//初始化图
bool connect_net();//判断整个网络是否可以连接
void dfs(int);//图的遍历
void deal();//从终端获取信息,并处理
bool p_2_p(int, int);//判断两点是否可以通信

int main()
{
    scanf("%d", &vex_num);
    getchar();
    while( vex_num != 0 )
    {
        deal();//处理一组数据
        if( connect_net() )
        {
            printf("\tThe network is connected\n");
        }
       
        scanf("%d", &vex_num);
    }
    return 0;
}

/*
*从终端获取数据，并处理
*/
void deal()
{
    char str;
    int i, j;
    scanf("%c", &str);
    getchar();
    while( str != 'S' )
    {
        if( str == 'C' )
        {
            scanf("%d%d", &i, &j);
            getchar();
            if( p_2_p(i, j)== true )
            {
                printf("yes\n");
            }
            else
            {
                printf("no\n");
            }
        }
        if( str == 'I' )
        {
            scanf("%d%d", &i, &j);
            getchar();
            Graph[i][j] = 1;
            Graph[j][i] = 1;
        }
        scanf("%c", &str);
    }

    return;
}
/*
*判断两点i,j之间是否可以通信 如果可以返回true 否则返回false
*/
bool p_2_p(int i, int j)
{
    for(int k=1; k<=vex_num; ++k)
    {
        if( Graph[i][k]==1 )
        {
            if( k == j )
                return true;
            if( p_2_p(k, j) )
                return true;
        }
    }

    return false;
}

/*
*如果可以连接成功则返回true否则返回false
*/
bool connect_net()
{//采用dfs遍历图
    init_traverse();
   
    dfs(1);//从1开始
   
    for( int i=1; i<=vex_num; ++i )
    {
        if( traverse[i]==false )
        {
            return false;
        }
    }

    return true;
}

void dfs(int i)
{
    traverse[i] = true;
    for( int j=1; j<NODE; ++j )
    {
        if( Graph[i][j]==1 )
        {
            if( !traverse[j] )
            {
                dfs(j);
            }
        }
    }
}

void init_traverse()
{
    int i=0;
    while(i < NODE)
    {
        traverse[i] = false;//表示未访问
        ++i;
    }
}

void init_Graph()
{
    int i=0, j=0;
    while( i < NODE )
    {
        while ( j < NODE )
        {
            Graph[i][j] = 0;
            ++j;
        }
        ++i;
    }
}

图片附件: 游客没有浏览图片的权限，请登录或注册

第 4 楼

得分:0

如果是按照终端输入数据输完后完成后结果是一次性打印出来的可以加链表进行存储

第 5 楼

得分:0

int main()
{
    scanf("%d", &vex_num);
    getchar();
    while( vex_num != 0 )
    {
        init_Graph();//忘掉了这句
        deal();//处理一组数据
        if( connect_net() )
        {
            printf("\tThe network is connected\n");
        }

        scanf("%d", &vex_num);
    }
    return 0;
}

第 6 楼

得分:10

俺也发一个

程序代码：

#include <stdio.h>
#include <algorithm>

#define MAX_VERTEX 10001

int parent[MAX_VERTEX];
int size[MAX_VERTEX];

void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        parent[i] = i;
        size[i] = 1;
    }
}

void union_set(int setA, int setB)
{
    if(size[setA] >= size[setB])
    {
        size[setA] += size[setB];
        parent[setB] = setA;
    }
    else
    {
        size[setB] += size[setA];
        parent[setA] = setB;
    }
}

int find(int e)
{
    if (e == parent[e])
        return e;
    parent[e] = find(parent[e]);
    return parent[e];
}

int main(void)
{
    int n, count;
    int u, v, r1, r2;
    char oper;

    while(scanf("%d", &n) != EOF)
    {
        if (n == 0) break;
        init(n);
        while (scanf("%c", &oper) != EOF)
        {
            if (oper == 'I')
            {
                scanf("%d %d", &u, &v);
                r1 = find(u);
                r2 = find(v);
                if (r1 != r2)
                    union_set(r1, r2);
            }
            else if (oper == 'C')
            {
                scanf("%d %d", &u, &v);
                r1 = find(u);
                r2 = find(v);
                if (r1 != r2)
                    printf("no\n");
                else
                    printf("yes\n");
            }
            else if (oper == 'S')
            {
                for (int i = 1; i <= n; ++i)
                    find(i);
                std::sort(parent + 1, parent + n + 1);
                count = 1;
                for (int i = 2; i <= n; ++i)
                {
                    if (parent[i] != parent[i - 1])
                        count++;
                }
                if (count == 1)
                    printf("The network is connected\n\n");
                else
                    printf("There are %d components\n\n", count);
                break;
            }
        }
    }
    return 0;
}

第 7 楼

得分:0

回复楼主 SHENHUNTIAN

不是纯C语言，用了STL的sort，你可以用qsort来代替或者自己写排序函数

第 8 楼

得分:0

其实不用排序，是我想复杂了。。

程序代码：

#include <stdio.h>

#define MAX_VERTEX 10001

int parent[MAX_VERTEX];
int size[MAX_VERTEX];

void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        parent[i] = i;
        size[i] = 1;
    }
}

void union_set(int setA, int setB)
{
    if(size[setA] >= size[setB])
    {
        size[setA] += size[setB];
        parent[setB] = setA;
    }
    else
    {
        size[setB] += size[setA];
        parent[setA] = setB;
    }
}

int find(int e)
{
    if (e == parent[e])
        return e;
    parent[e] = find(parent[e]);
    return parent[e];
}

int main(void)
{
    // freopen("data.in", "r", stdin);
    int n, count;
    int u, v, r1, r2;
    char oper;

    while(scanf("%d", &n) != EOF)
    {
        if (n == 0) break;
        init(n);
        while (scanf("%c", &oper) != EOF)
        {
            if (oper == 'I')
            {
                scanf("%d %d", &u, &v);
                r1 = find(u);
                r2 = find(v);
                if (r1 != r2)
                    union_set(r1, r2);
            }
            else if (oper == 'C')
            {
                scanf("%d %d", &u, &v);
                r1 = find(u);
                r2 = find(v);
                if (r1 != r2)
                    printf("no\n");
                else
                    printf("yes\n");
            }
            else if (oper == 'S')
            {
                count = 0;
                for (int i = 1; i <= n; ++i)
                {
                    if (i == parent[i])
                        count++;
                }
                if (count == 1)
                    printf("The network is connected\n\n");
                else
                    printf("There are %d components\n\n", count);
                break;
            }
        }
    }
    return 0;
}

收到的鲜花

寒风中的细雨于 2011-01-05 22:59 送鲜花 15朵

第 9 楼

得分:0

都是高手