|
Colored Sticks
| Time Limit: 5000MS | | Memory Limit: 128000K | | Total Submissions: 32351 | | Accepted: 8536 |
Description
You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?
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 Input
blue red
red violet
cyan blue
blue magenta
magenta cyan
Sample Output
Possible
无向图存在欧拉路的充要条件为：
① 图是连通的；
② 所有节点的度为偶数，或者有且只有两个度为奇数的节点。
这里用了两种方法，一种是直接分配好内存，用时：985MS
#include <cstdio>
#include <cstring>
#include <iostream>
#define maxn 500500
using namespace std;
struct node {
int id;
node *next[30];
};
node *root;
node tree[maxn * 10];//先分配好内存。
int du[maxn], per[maxn], color;//color 编号
int ans = 0;
node *create(){
node *p = &tree[ans++];
for(int i = 0 ; i < 26; ++i)
p -> next[i] = NULL;
return p;
};
void insert (char *s, int id){
node *p = root;
for(int i = 0; s[i]; ++i){
int k = s[i] - 'a';
if(p -> next[k] == NULL)
p -> next[k] = create();
p = p ->next[k];
}
p -> id = id;
}
int search (char *s){
node *p = root;
for(int i = 0; s[i]; ++i){
int k = s[i] - 'a';
if(p -> next[k] == NULL)
return 0;
p = p -> next[k];
}
return p->id;
}
void init(){
for(int i = 1; i <= maxn; ++i)
per[i] = i;
memset(du, 0 ,sizeof(du));
color = 0;
}
int find(int x){
int r = x;
while( r != per[r])
r = per[r];
per[x] = r;
return r;
}
void join (int x, int y){
int fx = find(x);
int fy = find(y);
per[fx] = fy;
}
bool judge(){
int sum = 0;
for(int i = 1; i <= color; ++i)
if(du[i] % 2 == 1) sum++;
if(sum != 0 && sum != 2) return false;
int k = find(1);
for(int i = 2; i <= color; ++i)
if(k != find(i))
return false;
return true;
}
int main (){
char s1[15], s2[15];
init();
root = create();
while(cin >> s1 >> s2){
int x = search(s1);
int y = search(s2);
if(!x) insert(s1,x = ++color);
if(!y) insert(s2,y = ++color);
du[x]++, du[y]++;
join(x, y);
}
if(judge())
printf("Possible\n");
else
printf("Impossible\n");
return 0;
}
第二种，动态分配内存，用时久一点：
1860MS
#include <cstdio>
#include <cstring>
#include <iostream>
#define maxn 500500
using namespace std;
struct node {
int id;//纪录颜色的编号
node *next[30];
};
node *root;
//node tree[maxn * 10];//先分配好内存。
int du[maxn], per[maxn], color;
//int ans = 0;
//node *create(){
// node *p = &tree[ans++];
// for(int i = 0 ; i < 26; ++i)
// p -> next[i] = NULL;
// return p;
//};
void insert (char *s, int id){
node *p = root;
for(int i = 0; s[i]; ++i){
int k = s[i] - 'a';
if(p -> next[k] == NULL){
node *q = new node;
memset(q -> next,NULL,sizeof(q -> next));
p -> next[k]= q;
}
p = p ->next[k];
}
p -> id = id;
}
int search (char *s){
node *p = root;
for(int i = 0; s[i]; ++i){
int k = s[i] - 'a';
if(p -> next[k] == NULL)
return 0;
p = p -> next[k];
}
return p->id;
}
void init(){
for(int i = 1; i <= maxn; ++i)
per[i] = i;
memset(du, 0 ,sizeof(du));
color = 0;
}
void initroot(){
root = new node;
memset(root -> next, NULL, sizeof(root->next));
}
int find(int x){
int r = x;
while( r != per[r])
r = per[r];
per[x] = r;
return r;
}
void join (int x, int y){
int fx = find(x);
int fy = find(y);
per[fx] = fy;
}
bool judge(){
int sum = 0;
for(int i = 1; i <= color; ++i)
if(du[i] % 2 == 1) sum++;
if(sum != 0 && sum != 2) return false;
int k = find(1);
for(int i = 2; i <= color; ++i)
if(k != find(i))
return false;
return true;
}
int main (){
char s1[15], s2[15];
init();
initroot();
//root = create();
while(cin >> s1 >> s2){
int x = search(s1);
int y = search(s2);
if(!x) insert(s1,x = ++color);
if(!y) insert(s2,y = ++color);
du[x]++, du[y]++;
join(x, y);
}
if(judge())
printf("Possible\n");
else
printf("Impossible\n");
return 0;
}
| 
转播
