首页 > 代码库 > poj 1386 欧拉回路判定
poj 1386 欧拉回路判定
奇怪的是,我的判定是不是联通的部分出问题了
先贴个对的:
#include <cstdio> #include <map> #include <cstring> #include <string> #include <iostream> using namespace std; const int SIZE = 100000+10; const int SSIZE = 1000 +10; const int tb = 26; int idx(char x) { return x-'a'; } int n,parent[tb],ideg[tb],odeg[tb],e[tb]; void init() { for(int i=0;i<tb;i++) { parent[i]=i; e[i]=ideg[i]=odeg[i]=0; } } int Find(int x) { if(x!=parent[x])parent[x]=Find(parent[x]); return parent[x]; } void Union(int x, int y) { x=Find(x); y=Find(y); if(x!=y)parent[y]=x; } int main() { //freopen("poj1386.txt","r",stdin); int ncase; char str[SIZE]; scanf("%d",&ncase); while(ncase--) { int u,v; scanf("%d",&n); init(); for(int i=0;i<n;i++) { scanf("%s",str); ideg[ u=idx( str[strlen(str)-1]) ]++; odeg[ v=idx( str[0]) ]++; e[u]=e[v]=1; Union(u, v); } int connect=1,tmp=Find(u); for(int i=0;i<tb;i++) { if(e[i]&&tmp!=Find(i)) { connect=0; break; } } if(!connect) { printf("The door cannot be opened.\n"); continue; } /*int scnt=0; for(int i=0;i<tb;i++) if(e[i] && Find(i) == i) scnt++; if(scnt>1) { printf("The door cannot be opened.\n"); continue; }*/ int acnt=0,bcnt=0,cnt=0; for(int i=0;i<tb;i++) if(e[i]) { if(ideg[i] == odeg[i])continue; if(ideg[i] == odeg[i]+1 ) { acnt++; continue; } if(odeg[i] == ideg[i]+1 ) { bcnt++; continue; } cnt++; } //if(cnt){printf("The door cannot be opened.\n");continue;} if((!acnt&&!bcnt&&!cnt) || (acnt==1&&bcnt==1&&cnt==0))printf("Ordering is possible.\n"); //if(acnt<=1 && bcnt<=1)printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } return 0; }
但是这样判断联通就WA得很惨,不晓得为什么,求大神指教:
int connect=1,tmp,i; for(i=0;i<tb;i++) if(e[i]) { tmp=Find(i); // i--; break; } for(;i<tb;i++) if(e[i] && tmp!=Find(i)) { connect=0; break; }
poj 1386 欧拉回路判定
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。