首页 > 代码库 > 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
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=0; break; } } 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=-1; break; } } } 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算法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。