#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 500001
struct Trie
{
int num;
Trie* next[26];
} a[5000000];
Trie root;
int location, id;
int set[MAX];
void initial()
{
root.num= -1;
memset( root.next, 0, sizeof(root.next) );
location= 0, id= 1;
}
void insert( char* s )
{
Trie* r= &root;
while( *s )
{
int t= *s- 'a';
if( r->next[t]== NULL )
{
r->next[t]= a+ location;
a[location].num= -1;
memset( a[location].next, 0, sizeof( a[location].next ) );
location++;
}
r= r->next[t];
s++;
}
if( r->num== -1 ) r->num= id++;
}
int degree[MAX];
int search( char* s )
{
Trie* r= &root;
while( *s )
{
int t= *s- 'a';
if( r->next[t] ) r= r->next[t];
else return -1;
s++;
}
return r->num;
}
int find( int i )
{
while( i!= set[i] ) i= set[i];
return i;
}
void Union( int a, int b )
{
int ta= find(a), tb= find(b);
set[ta]= tb;
}
int main()
{
char s1[15],s2[15];
initial();
for( int i= 0; i< MAX; ++i ) { degree[i]= 0; set[i]= i; }
while( scanf("%s%s",s1, s2)!= EOF )
{
insert(s1); insert(s2);
int a= search(s1), b= search(s2);
degree[a]++, degree[b]++;
Union(a,b);
}
int m= 0;
for( int i= 1; i< id; ++i )
if( degree[i]& 1 ) m++;
int t= find(1);
for( int i= 2; i< id; ++i )
if( find(i)!= t )
{
m= -1;
break;
}
if( m== 0 || m== 2 ) puts("Possible");
else puts("Impossible");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#define MAX 500001
struct Node
{
int value, ID;
Node(){}
Node( int a, int b ): value(a), ID(b) {}
};
int set[MAX], id= 0;
std::vector<Node> dict[MAX<<1];
int degree[MAX];
int find( int i )
{
while( i!= set[i] ) i= set[i];
return i;
}
void Union( int a, int b )
{
int ta= find(a), tb= find(b);
set[ta]= tb;
}
int getvalue( char* s )
{
__int64 t= 0;
while( *s )
{
t= t* 128+ *s- 'a';
s++;
}
return t% 1000001;
}
int main()
{
char s1[15],s2[15];
for( int i= 0; i< MAX; ++i ) { degree[i]= 0; set[i]= i; }
while( scanf("%s%s",s1, s2)!= EOF )
{
int t= getvalue(s1),a,b;
if( dict[t].size()== 0 )
{
dict[t].push_back( Node(t,++id) );
a= id;
}
else if( dict[t].size()== 1 )
a= dict[t][0].ID;
else
{
bool ok= false;
for( size_t i= 0; i< dict[t].size(); ++i )
if( dict[t][i].value== t )
{
a= dict[t][i].ID;
ok= true;
break;
}
if( !ok ) { dict[t].push_back( Node(t,++id) ); a= id; }
}
t= getvalue(s2);
if( dict[t].size()== 0 )
{
dict[t].push_back( Node(t,++id) );
b= id;
}
else if( dict[t].size()== 1 )
b= dict[t][0].ID;
else
{
bool ok= false;
for( size_t i= 0; i< dict[t].size(); ++i )
if( dict[t][i].value== t )
{
b= dict[t][i].ID;
ok= true;
break;
}
if( !ok ) { dict[t].push_back( Node(t,++id) ); b= id; }
}
degree[a]++, degree[b]++;
Union(a,b);
}
int m= 0;
for( int i= 1; i<= id; ++i )
if( degree[i]& 1 ) m++;
int t= find(1);
for( int i= 2; i<= id; ++i )
if( find(i)!= t )
{
m= -1;
break;
}
if( m== 0 || m== 2 ) puts("Possible");
else puts("Impossible");
return 0;
}
posted on 2008-11-25 10:31
Darren 阅读(196)
评论(0) 编辑 收藏 引用