题目大意:给定一些木棒,木棒两端都涂上颜色,求是否能将木棒首尾相接,连成一条直线,要求不同木棒相接的一边必须是相同颜色的。
我们把颜色看做点,木棒看做边,这道题就转为了求是否存在欧拉路。
而判断欧拉路只要看两点 ①图连通 ②所有节点的度为偶数或只有两个奇数度节点。
判断①我们可以使用并查集且必须压缩路径,否则会超时。而并查集需要利用数组下标,但读入为字符串,并且有25w条边,使用hash会超时。
这时候我们可以用trie(字典树),关于字典树可以自行百度。
#include <cstdio>#include <iostream>#include <cstring>#define maxn 500000using namespace std;struct Trie{ Trie* next[27]; bool flag; int id; Trie() { flag=false; id=0; memset(next,0,sizeof(next)); } }root;int tot;int dg[maxn+5];int fa[maxn+5];int trie(char *ch){ Trie* tree=&root; int len=0; while (ch[len]!='/0') { int pub=ch[len++]-'a'; if (!tree->next[pub]) tree->next[pub]=new Trie(); tree=tree->next[pub]; } if (tree->flag) return tree->id; else { tree->flag=true; tree->id=++tot; return tree->id=tot; }}int getf(int x){ if (fa[x]!=x) fa[x]=getf(fa[x]); return fa[x];}void ice_chair(int x,int y){ int fx=getf(y); int fy=getf(x); fa[fy]=fx; return ;}char a[15],b[15];int main(){ register int i,j; for (i=1;i<=maxn;i++) { fa[i]=i; } while(cin>>a>>b) { int x=trie(a); int y=trie(b); dg[x]++; dg[y]++; ice_chair(x,y); } int s=getf(1); int ans=0; for (i=1;i<=tot;i++) { if (dg[i]%2==1) ans++; if (ans>2) { PRintf("Impossible"); return 0; } if (getf(i)!=s) { printf("Impossible"); return 0; } } if (ans==1) printf("Impossible"); else printf("Possible"); return 0;}
新闻热点
疑难解答