Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我用深搜WA了,大家帮忙看一下

Posted by sunpy at 2008-08-02 10:06:24 on Problem 1847
#include<stdio.h>
#include<malloc.h>

#define N 101
#define M sizeof(struct ArcNode)

typedef struct ArcNode{
	int adjvex;
	struct ArcNode *next;
}ArcNode,*node;

typedef struct{
	int data;
	ArcNode *firstadj;
}AdjList[N];

typedef struct{
	AdjList vertices;
	int vexnum;
}AlGraph;
int visited[N],find=0;

int CreateAlG(AlGraph &G);
int dfs(AlGraph,int start,int des);

int main()
{
	AlGraph G;
	int start,des,s;
	scanf("%d %d %d",&G.vexnum,&start,&des);
	CreateAlG(G);
	for(int i=1;i<=G.vexnum ;i++)
		visited[i]=0;
	visited[start]=1;
	s=dfs(G,start,des);
	if(find)
		printf("%d",s);
	else
		printf("-1");
	return 0;
}


int  CreateAlG(AlGraph &G)
{
	int i,j;
	for(i=1;i<=G.vexnum;i++)
	{
		scanf("%d",&G.vertices[i].data);
		G.vertices[i].firstadj=NULL;
		node p,q;
		for(j=1;j<=G.vertices[i].data;j++)
		{	
			p=(node)malloc(M);
			if(!p)
				return 0;
			scanf("%d",&p->adjvex);
			p->next=NULL;
			if(j==1)
				G.vertices[i].firstadj=p;
			else
				q->next=p;
			q=p;
		}
	}
	return 0;
}

int dfs(AlGraph G,int start,int des)
{
	int s=0,j;
	node p;
	if(start==des)
	{
		find=1;
		return s;
	}
	for(p=G.vertices[start].firstadj;p;p=p->next,s++)
	{
		j=p->adjvex;
		if(!visited[j])
		{
			visited[j]=1;
			int temp=dfs(G,j,des);
			if(find==1)
			{
				s+=temp;
				break;
			}
		}
	}
	return s;
}
	
	



Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator