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

DPS 判连通性已AC。楼下肯定是你程序的问题。

Posted by dongshimou at 2014-07-07 00:09:58 on Problem 1386
贴上代码:

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
using namespace std;
int n,m;
int g[27][27];
int in[27],out[27];
bool vis[27];
int start;
int Euler()
{
    int I=0,O=0;
    for(int i=0; i<26; i++)
    {
        if(in[i]==out[i]+1)I++;
        else if(out[i]==in[i]+1)O++,start=i;
        else if(in[i]!=out[i])return 0;
    }
    if((I==0&&O==0)||(I==1&&O==1))return 1;
    return 0;
}
void dfs(int i)
{
    int j;
    for( j=0; j<26; j++)
    {
        if(g[i][j]==0)continue;
        g[i][j]--;
        vis[i]=vis[j]=1;
        dfs(j);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&m);
        char str[1001];
        memset(g,0,sizeof(g));
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        for(int i=0; i<m; i++)
        {
            scanf("%s",str);
            int u=str[0]-'a';
            int v=str[strlen(str)-1]-'a';
            g[u][v]++;
            in[v]++,out[u]++;
        }
        for(int i=0;i<26;i++)
        if(out[i]>0){start=i;break;}
        bool flag=1;
        flag=Euler();
        if(!flag)
        {
            puts("The door cannot be opened.");
            continue;
        }
        memset(vis,0,sizeof(vis));
        dfs(start);
        for(int i=0; i<26; i++)
        {
            if(in[i]||out[i])
            {
                if(vis[i]==0)
                {
                    flag=0;
                    break;
                }
            }
        }
        if(flag)puts("Ordering is possible.");
        else puts("The door cannot be opened.");
    }
}

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