首页 > 代码库 > UPC 2170 D Equal Is Not Really Equal (欧拉路径)
UPC 2170 D Equal Is Not Really Equal (欧拉路径)
题目链接:http://acm.upc.edu.cn/problem.php?id=2170
题意:给出一个字符串,比如ABACA,在这个串里,AB、BA、AC、CA各出现一次。若存在另外一个串,里面也AB、BA、AC、CA各出现一次。我们称ABACA是不唯一的。给出一个串,判断其是不是唯一。
思路:将字母看做顶点,将相邻的连有向边。那么题 目转化成这个图是不是存在两条欧拉路径。现在这个图至少有一条欧拉路径。设原串最后一个字母对应的节点为end。那么现在的图中若存在一个点u,对于这个 u至少有两个节点v1,v2,使得存在<u,v1><u,v2>,并且删掉两个中的任意一条后end都可由u到达,则说明有两个 欧拉路径。我们现在假设u只有这两个子节点v1,v2,那么原来的欧拉回路必然是走的<u,v1>或者 <u,v2>,不妨是<u,v1>,那么对于u、v1、v2、end四个点的顺序大致有两种情况:
(1)u->v1->v2->u->v2->end
(2)u->v1->u->v2->end
那么对于边<u,v2>,若将其删除后,如能够到达end,那么只能是情况(1),此时两条欧拉路径除了(1)之外另一条是u->v2->u->v1->v2->end。另外有一种情况上面的算法不能涉及,就是ABCDA,也就是前后两个是一样的情况,这个必然是不唯一的,因为你存在了环,如BCDAB,CDABC等。
int a[30][30],d[30];char s[N];int n,end,flag;int allSame(){ int i; FOR0(i,n) if(s[i]!=s[0]) return 0; return 1;}int h[30],last;void DFS(int x){ h[x]=1; int i; FOR0(i,26) if(!h[i]&&a[x][i]) DFS(i);}int OK(int x){ clr(h,0); DFS(x); return h[last];}void deal(){ int cnt,i,j; FOR0(i,26) if(d[i]>1) { cnt=0; FOR0(j,26) if(a[i][j]>0) { a[i][j]--; if(OK(i)) cnt++; a[i][j]++; } if(cnt>1) { puts("not unique"); return; } } puts("unique");}int main(){ rush() { RD(s); n=strlen(s); int i,j; clr(a,0); clr(d,0); FOR0(i,n-1) { a[s[i]-‘A‘][s[i+1]-‘A‘]++; } FOR0(i,26) FOR0(j,26) if(a[i][j]) d[i]++; if(!allSame()&&s[0]==s[n-1]) { puts("not unique"); continue; } last=s[n-1]-‘A‘; deal(); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。