?
Input Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.?
Output If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.?
Sample Inputblue red red violet cyan blue blue magenta magenta cyan?
?
Sample OutputPossible?????????? ????????? 题目大意：给你很多对单词，单词相当于一个点，一对单词相当于一条边，问这么多对的单词能否组成一条欧拉路，要求每条边都要经过。题目数据很大，每个单词最多10个字母，之前用map映射，把字母映射成编号，但是速度太慢，一直TLE，后来换成字典树，字典树速度才行，连通性就用并查集，判断欧拉路是否组成，就看度数是奇数的个数是否是0或者2。 链接：http://poj.org/problem?id=2513 代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <map>
using namespace std;
struct node
{
int x;
node *next[26];
};
int deg[510005], father[510005], cnt, ant;
node *root, memory[5100050];
node *create()
{
node *p = &memory[ant++];
int i;
for(i = 0; i < 26; i++)
{
p->next[i] = NULL;
}
return p;
};
void insert(char *s, int x)
{
node *p = root;
int i, k;
for(i = 0; s[i]; i++)
{
k = s[i] - 'a';
if(p->next[k] == NULL)
{
p->next[k] = create();
}
p = p->next[k];
}
p->x = x;
}
int search(char *s)
{
node *p = root;
int i, k;
for(i = 0; s[i]; i++)
{
k = s[i] - 'a';
if(p->next[k] == NULL) return 0;
p = p->next[k];
}
return p->x;
}
void init()
{
int i;
for(i = 1; i <= 510000; i++)
{
father[i] = i;
}
memset(deg, 0, sizeof(deg));
cnt = 0;
}
int find(int x)
{
if(x != father[x])
{
father[x] = find(father[x]);
}
return father[x];
}
void Union(int x, int y)
{
father[x] = y;
}
bool judge() //判断是否满足欧拉
{
int i, k, odd = 0;
for(i = 1; i <= cnt; i++)
{
if(deg[i]%2 == 1) odd++;
}
if(odd != 0 && odd != 2) return false;
k = find(1);
for(i = 2; i <= cnt; i++)
{
if(k != find(i)) return false;
}
return true;
}
int main()
{
int x, y, fx, fy;
char s1[15], s2[15];
init();
root = create();
while(scanf("%s %s", s1, s2) != EOF)
{
x = search(s1); //映射求编号速度太慢
y = search(s2); //用字典树来求编号
if(x == 0) insert(s1, x = ++cnt);
if(y == 0) insert(s2, y = ++cnt);
deg[x]++;
deg[y]++;
fx = find(x);
fy = find(y);
if(fx != fy) Union(fx, fy);
}
if(judge()) printf("Possible\n");
else printf("Impossible\n");
return 0;
}
?
相关文章
