| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:找着别人AC的代码对比了一下 没发现思想有错 可就是WA 大虾帮忙啊。。。。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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator