博客

#include
<
iostream
>

#include
<
stdio.h
>


using

namespace
std;

#define
MAX 27


#define
S 500003


struct
Node
{

int
id;
Node
*
next[MAX];

};

bool
judge_con();

bool
judge_fre( );
Node
*
InitNode();

int
fre[S];

int
father[S];

int
Insert(Node
*
,
char

*
);

int
getfather(
int
);

int
sum
=-
1
;

int
main()
{

for
(
int
i
=
0
;i
<
S;i
++
)
father[i]
=
i;

int
x;

int
y;
Node
*
head
=
InitNode();

char
a[
12
];
char
b[
12
];

while
(cin
>>
a){
//
用while(scanf(“%s%s”,a,b)!=EOF) 省时间


cin
>>
b;
x
=
Insert(head,a);
y
=
Insert(head,b);

father[getfather(x)]
=
getfather(y);
fre[x]
++
;
fre[y]
++
;
}

if
(judge_fre()
&&
judge_con())
cout
<<
“
Possible
“
;

else
cout
<<
“
Impossible
“
;

}

int
getfather(
int
i)
{

if
(father[i]
!=
i)
{
father[i]
=
getfather(father[i]);
}

return
father[i];
}

int
Insert(Node
*
h,
char

*
p)
{
Node
*
tmp;
tmp
=
h;

int
i
=
0
;

int
num;

while
(p[i] )
{
num
=
p[i]
–
‘
a
‘
;

if
(tmp
->
next[num]
!=
NULL)
tmp
=
tmp
->
next[num];

else
{
tmp
->
next[num]
=
InitNode();
tmp
=
tmp
->
next[num];
}
i
++
;
}

if
(tmp
->
id
==-
1
)
{sum
++
;
//
竟然在这里忘记了括号


tmp
->
id
=
sum;
}

return
tmp
->
id;
}
Node
*
InitNode()
{
Node
*
p
=
new
Node ;
p
->
id
=-
1
;

for
(
int
i
=
0
;i
<
MAX;i
++
)
p
->
next[i]
=
NULL;

return
p;
}

bool
judge_fre( )
{

int
i
=
0
;
int
k
=
0
;

for
(i
=
0
;i
<=
sum;i
++
)

if
(fre[i]
%
2
!=
0
)
k
++
;

if
(k
==
0
||
k
==
2
)

return

true
;

else

return

false
;
}

bool
judge_con()
{

int
j
=
0
;

int
x
=
getfather(
0
);

for
( j
=
0
;j
<=
sum;j
++
)

if
(getfather(j)
!=
x)

break
;

if
(j
==
sum
+
1
)

return

true
;

else

return

false
;
}

 

这题 开始 RE 了好多回  后来才发现是数组开小了  才导致指针越界    还是应该仔细看题   S开始弄成了250003

此题做法是 字典树+并查集             就是一个hash映射问题