POJ 2513 trie树+并查集判断无向图的欧拉路
2024-08-25 23:18:56
生无可恋
查RE查了一个多小时。。
原因是我N define的是250500
应该是500500!!!!!!!!!
身败名裂,已无颜面对众人。。
吐槽完了 我们来说思路。。。
思路:
判有向图能否形成欧拉路
但是他给的是string,怎么转化成int呢?
trie树!
这东西有多么优美我就不说了。。。
反正写起来不难。
具体的请见代码吧
// by SiriusRen
#include <bitset>
#include <cstdio>
#define N 500500
using namespace std;
bitset<N>b;
int tot=0,num=0,f[N],n,m,ansx=0,ans=0,v[N],trie[N*10][27];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int get(){
int jy=0;char p=getchar();
if(p==EOF)return 0;
while(p>'z'||p<'a')p=getchar();
while(p>='a'&&p<='z'){
if(trie[jy][p-'a']==-1){
trie[jy][p-'a']=++tot;
jy=trie[jy][p-'a'];
for(int i=0;i<26;i++)trie[jy][i]=-1;
}
else jy=trie[jy][p-'a'];
p=getchar();
}
if(!trie[jy][26])return trie[jy][26]=++num;
else return trie[jy][26];
}
int main(){
for(int i=0;i<26;i++)trie[0][i]=-1;
for(int i=1;i<=500000;i++)f[i]=i;
while(n=get()){
m=get();
v[m]++;v[n]++;
f[find(n)]=find(m);
}
for(int i=1;i<=num;i++)
if(!b[find(i)])b[find(i)]=1,ans++;
for(int i=1;i<=num;i++)
if(v[i]&1)ansx++;
if(ans<=1&&(ansx==0||ansx==2))puts("Possible");
else puts("Impossible");
}
这一版都是我刷的。。。。包括vjudge。。。。。。
最新文章
- 如果你遇到,在IntelliJ IDEA里Ctrl+Alt+方向键用不了
- c#之委托所有方法
- 在VMware虚拟机中配置DOS汇编开发环境!!
- java io知识点汇总FIle类
- 有关按位DP
- WinFrom 安装包制作
- android 26 设置项目有多个入口Activity。
- getting start with storm 翻译 第八章 part-1
- 【剑指offer】面试题36:数组中的逆序对
- AndroidTestCase测试用法
- codevs1304 拓扑序计数
- Windows Server 2012 R2超级虚拟化之六 Hyper-v Replica 2.0和Live migrations
- CheckBoxList的操作查询是否被选中设置或者得到
- JS事件流理解
- 201521123040《Java程序设计》第12周学习总结
- SpringCloud学习系列之六 ----- 路由网关Zuul基础使用教程
- 【Python3爬虫】最新的模拟登录新浪微博教程
- webbrowser设置为相应的IE版本
- 【转】redis-cluster安装配置
- linux 创建用户和添加到组