程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Codeforces Round #288 (Div. 2) D.Tanya and Password(歐拉路徑)

Codeforces Round #288 (Div. 2) D.Tanya and Password(歐拉路徑)

編輯：關於C++

第一次做輸出歐拉路徑的題。用dfs搜。

先對每個單詞拆成前兩個一組，後兩個一組，然後對這兩組加邊並標號。比如“abc”，拆成“ab”和“bc”，然後對ab和bc所屬的編號加邊。然後深搜，並記錄路徑。需要注意的是，用前向星的話，需要再深搜的時候讓前面走過的邊後邊不用再走，而且也要回溯的時候後邊走過的前面的也不再走。簡單處理下就行了。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
int in[4000], out[4000], cnt, head[4000], tot, vis[210000], path[210000], top;
char st[210000][4];
int id[4000];
struct node {
        int u, v, next;
} edge[410000];
void add(int u, int v)
{
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt++;
}
void dfs(int u, int id)
{
        for(int i=head[u]; i!=-1; i=edge[i].next) {
                if(!vis[i]) {
                        vis[i]=1;
                        head[u]=i;
                        dfs(edge[i].v,i);
                }
                i=head[u];
        }
        path[top++]=id;
}
int getid(char *s)
{
        int ans=0,tmp;
        for(int i=0;i<2;i++){
                if(s[i]>='a'&&s[i]<='z') tmp=s[i]-'a';
                else if(s[i]>='A'&&s[i]<='Z') tmp=s[i]-'A'+26;
                else tmp=s[i]-'0'+52;
                ans=ans*62+tmp;
        }
        return ans;
}
void init()
{
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(id,0,sizeof(id));
        cnt=tot=0;
}
int main()
{
        int n, i, flag, sum=0, pos, num1, num2;
        char s1[3], s2[3];
        scanf(%d,&n);
        init();
        getchar();
        for(i=0; i1) {
                        flag=1;
                        break;
                }
        }
        if(flag||sum>2) {
                printf(NO
);
        } else {
                top=0;
                dfs(pos,-1);
                //printf(%d
,top);
                if(top!=n+1) {
                        printf(NO);
                } else {
                        printf(YES
);
                        //printf(---%d
,path[top-2]);
                        printf(%s,st[path[top-2]]);
                        for(i=top-3; i>=0; i--) {
                                printf(%c,st[path[i]][2]);
                        }
                }
        }
        return 0;
}