首页 > 代码库 > codeforces 508 D. Tanya and Password (fleury算法)

codeforces 508 D. Tanya and Password (fleury算法)

codeforces 508 D. Tanya and Password (fleury算法)

题目链接:

http://codeforces.ru/problemset/problem/508/D

题意:
给出n个长度为3的字符串,如:abc bca aab 如果一个字符串的长度为2的后缀等于,另外一个字符串的长度为2的前缀,则这两个字符串能连起来,比如:aabca,然后这n个字符串可以形成一个图,求图上的一条欧拉通路。
限制:
1 <= n <= 2*10^5,字符串里面有大写字母,小写字母
思路:
把每个字符串当成边,其前缀后缀当作点,如:abc -> ab到bc。
则这个问题化为:有62*62个点,2*10^5条边的图,求一条欧拉通路的题目。
用fleury(弗罗莱),个人感觉用邻接表实现效率比邻接矩阵

ps:这道题dfs会爆栈,把它改成非递归的就行。


附上fleury算法链接

http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html


 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/*codeforces 508 D. Tanya and Password
  题意:
  给出n个长度为3的字符串,如:abc bca aab 如果一个字符串的长度为2的后缀等于,另外一个字符串的长度为2的前缀,则这两个字符串能连起来,比如:aabca,然后这n个字符串可以形成一个图,求图上的一条欧拉通路。
  限制:
  1 <= n <= 2*10^5,字符串里面有大写字母,小写字母
  思路:
  把每个字符串当成边,其前缀后缀当作点,如:abc -> ab到bc。
  则这个问题化为:有62*62个点,2*10^5条边的图,求一条欧拉通路的题目。
  用fleury(弗罗莱),个人感觉用邻接表实现效率比邻接矩阵
  ps:这道题dfs会爆栈,把它改成非递归的就行。
  */

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<stack>
using namespace std;
const int M=200005;
const int N=65*65;
vector<int> mp[N];
int fa[N];
int in[N],out[N];
char ans[M],rev[M];
int len=0;
string i2s[N];
map<string,int> s2i;
int stk[M],top=0;

int getFa(int x){
    if(x!=fa[x]) return fa[x]=getFa(fa[x]);
    return x;
}
void dfs(int x){
    while(mp[x].size()>0){
        stk[++top]=x;
        int ch=mp[x][mp[x].size()-1];
        mp[x].pop_back();
        x=ch;
    }
    stk[++top]=x;
}
void fleury(int S){
    int brige;
    stk[++top]=S;
    int flag=0;
    int tp;
    while(top>0){
        tp=stk[top--];
        brige=(mp[tp].size()==0);
        if(brige){
            if(flag)
                ans[len++]=i2s[tp][0];
            else{
                ans[len++]=i2s[tp][1];
                ans[len++]=i2s[tp][0];
                flag=1;
            }
        }
        else
            dfs(tp);
    }
}

int main(){
    int n,m;
    char str[5];
    string fr,to;
    n=0;
    scanf("%d",&m);
    for(int i=0;i<65*65;++i)
        fa[i]=i;
    for(int i=0;i<m;++i){
        int x,y;
        int fx,fy;
        scanf("%s",str);
        fr=str[0];
        fr+=str[1];
        to=str[1];
        to+=str[2];

        x=s2i[fr];
        if(x==0){ s2i[fr]=++n; i2s[n]=fr; x=n; }
        y=s2i[to];
        if(y==0){ s2i[to]=++n; i2s[n]=to; y=n; }

        mp[x].push_back(y);
        fx=getFa(x);
        fy=getFa(y);
        if(fx!=fy)
            fa[fy]=fx;
        ++out[x];
        ++in[y];
    }
    int lt=1;
    int root=getFa(1);
    for(int i=2;i<=n;++i){
        if(getFa(i)!=root){ lt=0break; }
    }
    int S=0,T=0,cnt=0;
    for(int i=1;i<=n;++i){
        if(in[i]==out[i]) continue;
        else{
            cnt++;
            if(in[i]-out[i]==1) T=i;
            else if(in[i]-out[i]==-1) S=i;
            else{ cnt=-1break; }
        }
    }
    if(lt && ((cnt==2 && S!=T) || cnt==0)){
        puts("YES");
        if(cnt==0) S=1;
        fleury(S);
        int len=strlen(ans);
        for(int i=0;i<len;++i){
            rev[len-1-i]=ans[i];
        }
        puts(rev);
    }
    else{
        puts("NO");
    }
    return 0;
}

codeforces 508 D. Tanya and Password (fleury算法)