题意:

有很多棒子,两端有颜色,告诉你两端的颜色,让你把这些棒子拼接起来要求相邻的接点的两个颜色是一样的。

问能否拼接成功。

思路:

将颜色看作节点,将棒子看作边,寻找欧拉通路。

保证图的连通性的时候用到并查集。

这里颜色由于是字符串代替,所以需要用到字典树优化离散化过程。

字典树的学习感谢博客http://www.ahathinking.com/archives/14.html

重点是这个图很棒:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<iostream>
#include<stdlib.h>
using namespace std;
int me[*+];
int out[];
struct ti
{
void add(char *,int);
int findi(char *);
ti *mine[];
int num;
};
void ti::add(char *s,int tmp)
{
int len=strlen(s);
ti *next=this;
for(int i=;i<len;i++)
{
if(next->mine[s[i]-]==NULL)
{
next->mine[s[i]-]=(ti*)malloc(sizeof(ti));
memset(next->mine[s[i]-]->mine,NULL,sizeof(mine));
next->mine[s[i]-]->num=;
}
next=next->mine[s[i]-];
}
next->num=tmp;
}
int ti::findi(char *s)
{
int len=strlen(s);
ti *next=this;
for(int i=;i<len;i++)
{
if(next->mine[s[i]-]==NULL)
{
return ;
}
next=next->mine[s[i]-];
}
return next->num;
}
ti tree;
int findme(int n)
{
if(n!=me[n])
return me[n]=findme(me[n]);
return n;
}
int main()
{
memset(tree.mine,NULL,sizeof(tree.mine));
tree.num=;
char col1[],col2[];
for(int i=;i<=;i++)
{
me[i]=i;
}
int num=;
while(scanf("%s%s",col1,col2)!=EOF)
{
if(tree.findi(col1)==)
{
num++;
tree.add(col1,num);
}
if(tree.findi(col2)==)
{
num++;
tree.add(col2,num);
}
int tmpa=findme(tree.findi(col1));
int tmpb=findme(tree.findi(col2));
if(tmpa!=tmpb)
me[tmpb]=tmpa;
out[tree.findi(col1)]++;
out[tree.findi(col2)]++;
}
int c=;
int x,y,z;
x=y=z=;
for(int i=;i<=num;i++)
{
if(me[i]==i)
c++;
if(out[i]&)
x++;
}
if(x==||c>||x>)
printf("Impossible\n");
else
printf("Possible\n");
}

最新文章

  1. 数据库设计中的Soft Delete模式
  2. iMac 升级到10.12后,蓝牙不能用
  3. 项目vue2.0仿外卖APP(二)
  4. 【数论】X problem
  5. ios打包
  6. 洛谷P2015 二叉苹果树
  7. Beaglebone Black的启动
  8. Smarty 变量使用
  9. listview前几个item的图片怎么是空白的、listview更新了ui不起作用、在handler里更新了UI不起作用
  10. python mysql 2014 Commands out of sync; you can&#39;t run this command now
  11. 【java】控制台实现贪吃蛇小游戏-LinkedList、Scanner
  12. git rejected - non-fast-forward
  13. SecureCRT的安装与破解(过程很详细!!!)
  14. MFC项目中:报错:“fatal error LNK1561: 必须定义入口点”解决方法
  15. 使用Metasploit渗透攻击windows系统(一)
  16. asp.net core mvc 中间件之WebpackDevMiddleware
  17. 前端开发笔记(2)css基础(上)
  18. dtcp格式定义
  19. Luogu 1070 道路游戏
  20. ubuntu16更新源

热门文章

  1. 10道有关ios的题
  2. 伪类的格式重点:父标签层级 &amp; 当前标签类型
  3. scriptPubKey and scriptSig
  4. 汇编3栈帧,参数传递,串操作,混合汇编,x64,asm文件
  5. Chrome浏览器商店安装的插件保存到本地
  6. OpenCV2:第三章 读取图像
  7. ES6 第五章 字符串的新增方法 具体参照 http://es6.ruanyifeng.com
  8. dns config
  9. js实现音量拖拽的效果模拟
  10. tornado框架基础07-sqlalchemy查询