游客 注册 | 登录
中文 | En

1491 - 连通图

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。

题目输入

每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。如果 n 为 0 表示输入结束。随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。

题目输出

对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。

输入/输出样例

输入格式

4 3
4 3
1 2
1 3
5 7
3 5
2 3
1 3
3 2
2 5
3 4
4 1
7 3
6 2
3 1
5 6
0 0

输出格式

YES
YES
NO

C语言解答

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 1001
typedef int WeightType;
typedef int Elemtype;
typedef struct EdgeNode
{
    int adjvex;
    WeightType weight;
    struct EdgeNode *next;
}EdgeNode;

typedef struct VexNode
{
    EdgeNode *firstarc;
}VexNode, AdjList[MAXVEX];

typedef struct GraphADJ{
    AdjList adjlist;
    int numvex, numedge;
}GraphADJ;

void InitGraph(GraphADJ *G,int n)
{
    int i;
    G->numvex = n;
    for(i=1; i<=n; i++)
		G->adjlist[i].firstarc = NULL;
}
void InsertEdge(GraphADJ *G,int s,int t,int w)
{
    EdgeNode *newn = (EdgeNode *)malloc(sizeof(EdgeNode));
    newn->adjvex = t;
    newn->weight = w;
    newn->next = G->adjlist[s].firstarc;
    G->adjlist[s].firstarc = newn;
	
}
int LocateEdge(GraphADJ G,int s,int t)
{
    EdgeNode *p = G.adjlist[s].firstarc;
    while(p!=NULL)
	{
        if(p->adjvex == t)
            return 0;
        p = p->next;
    }
    return 1;
}
int Create(GraphADJ *G,int n,int m)
{
	int s,t,i,x;
	int j=0;
	int a[1010],visit[2000];
	InitGraph(G,n);
	for(i=1;i<=n;i++)
		visit[i]=0;
	for(i=0;i<m;i++)
	{
		scanf("%d%d",&s,&t);
		x=LocateEdge(*G,s,t);
        if(x==1)
		{
            InsertEdge(G,s,t,1);
            InsertEdge(G,t,s,1);
        }
	}
    EdgeNode *p;
	i=1;
    do
	{
	  p=G->adjlist[i].firstarc;
	  visit[i]=1;
	  while(p!=NULL)
	  {
	       i=p->adjvex;
		   if(visit[i]!=1)
		   {
	       a[j++]=i;
           visit[i]=1;
		   }
	       p=p->next;
	  }
	  j--;
	  if(j>=0)
	    i=a[j];
	}while(j>=0);
	for(i=1;i<=n;i++)
	{
		if(visit[i]==1);
		else
		   return 0;
	}
	return 1;
}
void main()
{
	int n,m,x;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
	   if(n==0&&m==0)
		  break;
	   GraphADJ G;
	   x=Create(&G,n,m);
	   if(x)
		   printf("YES\n");
	   else
		   printf("NO\n");
	}
}

C++解答

#include <stdio.h>
int n,m;
int a[1111][1111],b[1111],t;
void dd(int x)
{
	int i;
	b[x]=1;
	t++;
	for(i=1;i<=n;i++)
		if((a[x][i]==1)&&(b[i]==0))
			dd(i);
}
int run()
{
	int i,j,k;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			a[i][j]=0;
	for(i=1;i<=n;i++)
		b[i]=0;
	t=0;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&j,&k);
		a[j][k]=1;
		a[k][j]=1;
	}
	dd(1);
	if(t<n)
		printf("NO\n");
	else
		printf("YES\n");
}
int main()
{
	scanf("%d%d",&n,&m);
	while(n!=0)
	{
		run();
		scanf("%d%d",&n,&m);
	}
	return 0;
}
请先登陆