我真的是呵呵這道題了 //第二次更新，發(fā)現(xiàn)我是sb，并查集寫(xiě)錯(cuò)了，哈哈哈哈哈,之前能過(guò)真是奇跡

void unionn(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy)f[fy]=fx;
}

歐拉通路，有向圖，并查集+判斷入度出度（只能存在一對(duì)abs（入度-出度)==1）的，其他的都是入度等于出度

大不了并查集t了我，wa是幾個(gè)意思？

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
typedef long long ll;
const double pi=acos(-1.0);
const double E=2.718281828459;
using namespace std;
const int N=27;
char s[1100];
int in[N],out[N];
int f[N],vis[N];
void init()
{memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));memset(out,0,sizeof(out));for(int i=0;i<=N;i++)f[i]=i;
}
int find(int x)
{if(x==f[x]) return f[x];else return f[x]=find(f[x]);
}
void unionn(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy)f[fy]=fx;
}
int main()
{int T,t;int x,y;cin>>T;while(T--){init();scanf("%d",&t);while(t--){scanf("%s",s);int len=strlen(s);x=s[0]-'a';y=s[len-1]-'a';out[x]++,in[y]++;vis[x]=1,vis[y]=1;unionn(x,y);}int a=0,b=0,cnt=0,falg=0,mark=0;for(int i=0;i<26;i++){if(vis[i]){if(f[i]==i)cnt++;if(in[i]!=out[i]){if(in[i]-out[i]==1)a++;else if(out[i]-in[i]==1)b++;elsemark++;}if(cnt>1||mark){falg=1;break;}}}if(falg||mark)printf("The door cannot be opened.\n");else{if((a==1&&b==1)||(a==0&&b==0))printf("Ordering is possible.\n");elseprintf("The door cannot be opened.\n");}}return 0;
}

?

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 1386 Play on Words的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。