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:找着别人AC的代码对比了一下 没发现思想有错 可就是WA 大虾帮忙啊。。。。

Posted by wlp at 2008-09-19 10:01:53 on Problem 1386
In Reply To:找着别人AC的代码对比了一下 没发现思想有错 可就是WA 大虾帮忙啊。。。。 Posted by:qpwoei at 2007-08-17 00:11:23
> #include<iostream>
> using namespace std;
> 
> int degree[26],N,n;
> string s;
> bool adj[26][26],visited[26];
> 
> void Input()
> {
>  int i,j,t1,t2;
>  char ch,cht;
>  for(i=0;i<26;i++)
>  {
>   visited[i]=false;
>   degree[i]=0;
>   for(j=0;j<26;j++)
> 	  adj[i][j]=false;
>  }
> 
>  scanf("%d",&n);
>  getchar();
>  for(i=0;i<n;i++)
>  {
>   ch=getchar();
>   t1=ch-'a';
>   while(1)
>   {
>   cht=getchar();
>   if(cht>='a'&&cht<='z')ch=cht;
>   else if(cht=='\n')break;
>   }
>   t2=ch-'a';
>   adj[t1][t2]=true;
>   visited[t1]=true;
>   visited[t2]=true;
>   ++degree[t1];//入度
>   --degree[t2];//出度
>  }
> }
> 
> bool Deal()//根据欧拉回路的定义算出入度
> {
>  int i,f1,f2;
>  f1=f2=0;
>  for(i=0;i<26;i++)
> 	 if(degree[i]==1)f1++;
>      else if(degree[i]==-1)f2++;
> 	 else if(degree[i]!=0){return false;}
>  if((f1==1&&f2==1)||(f1==0&&f2==0))return true;
>  else return false;
> }
> 
> void DFS(const int &v)
> {
>  int i;
>  visited[v]=false;
>  for(i=0;i<26;i++)
> 	 if(adj[v][i]==true&&visited[i]==true)DFS(i);
> }
> int main()
> {
>  int i;
>  cin>>N;
>  while(N--)
>  {
>   Input();
>   if(!Deal())cout<<"The door cannot be opened."<<endl;
>   else {
>   for(i=0;i<26;i++)
>     if(visited[i]==true)break;
>   DFS(i);//访问到的都变成了false
>   for(i=0;i<26;i++)//再有true的点说明没有连通
> 	 if(visited[i]==true)break;
>    if(i==26)cout<<"Ordering is possible."<<endl;
>    else cout<<"The door cannot be opened."<<endl;
>   }
>  }
>  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