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

Re:不知道为何会wa....

Posted by 1224730131 at 2013-01-24 14:12:06 on Problem 1386
In Reply To:不知道为何会wa.... Posted by:ziyang at 2004-04-17 10:03:10
> 首先用DFS判断是否连通,若连通,再逐个检查其顶点的入度和出度,以判断是否有一条有向欧拉路。
> 可是为什么会WA????
> 
> #include<stdio.h>
> #include<string.h>
> 
> 	long adj[26][26],indeg[26],outdeg[26];
>    long visited[26];
>    long flag,flagin,flagout;
>    char mentioned[26];
>    long first,last;
>    long count;
>    long ment,i,j,v,t;
>    long n;
>    char input[1010];
> int main()
> {
>    long DFS(long);
>    scanf("%d",&v);
>    for(t=0;t<v;t++)
>    {
> 	   scanf("%d",&n);
> 	   for(i=0;i<26;i++) {visited[i]=0; indeg[i]=0; outdeg[i]=0; }
> 	   for(i=0;i<26;i++) for(j=0;j<26;j++) adj[i][j]=0;
> 	   ment=0;flagin=0;flagout=0;
> 	   count=0;
> 	   for(i=0;i<n;i++)
> 	   {
> 		   scanf("%s",input);
> 		   first=input[0]-97;last=input[strlen(input)-1]-97;
> 		   for(j=0;j<ment;j++)
> 			   if((long)mentioned[j]-97==first) break;
> 		   if(j==ment) mentioned[ment++]=first+97;
> 		   for(j=0;j<ment;j++)
> 			   if((long)mentioned[j]-97==last) break;
> 		   if(j==ment) mentioned[ment++]=last+97;
> 		   adj[first][last]=1;
> 		   outdeg[first]++;indeg[last]++;
> 	   }
> 	   DFS((long)mentioned[0]-97);
> 	   if(count!=ment)
> 	   {
> 	      printf("The door cannot be opened.\n"); continue;
> 	   }
> 	   flag=1;
> 	   for (i=0;i<26;i++)
> 	   {
> 		   if(indeg[i]==outdeg[i]) continue;
> 		   if(indeg[i]>outdeg[i]+1 || outdeg[i]>indeg[i]+1) {flag=0;break;}
> 		   if(indeg[i]==outdeg[i]+1) {flagin++; continue;}
> 		   if(indeg[i]==outdeg[i]-1) {flagout++;continue;}
> 	   }
> 	  
> 	   if(flag==0 || flagin>1 || flagout>1 ||flagin!=flagout)
> 		   {
> 	      printf("The door cannot be opened.\n"); continue;
> 	   }
> 	   printf("Ordering is possible.\n");
>    }
>    return 0;
> }
> long DFS(long ch)
> {
>     
> 	count++;
> 	visited[ch]=1;
> 	for(i=0;i<26;i++)
> 	{
> 		if(adj[ch][i]>=1 && visited[i]==0) DFS(i);
> 	}
> 	for(i=0;i<26;i++)
> 	{
> 		if(adj[i][ch]>=1 && visited[i]==0) DFS(i);
> 	}
> 	return 0;
> }

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