#include
<
iostream
>
#include
<
stack
>
#include
<
vector
>
int
n, m;
int
degree[
26
];
int
data[
26
][
26
];
bool
exist[
26
];
![](/Images/OutliningIndicators/None.gif)
std::vector
<
char
>
re;
![](/Images/OutliningIndicators/None.gif)
int
length()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int
num
=
0
;
for
(
int
i
=
0
; i
<
n;
++
i )
if
( exist[i] )
num
++
;
![](/Images/OutliningIndicators/InBlock.gif)
return
num;
}
int
toplogicalsort()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
std::stack
<
char
>
st;
int
*
d
=
new
int
[n];
![](/Images/OutliningIndicators/InBlock.gif)
re.clear ();
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
i
=
0
; i
<
n;
++
i )
d[i]
=
degree[i];
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
i
=
0
; i
<
n;
++
i )
if
( d[i]
==
0
&&
exist[i] )st.push(i);
![](/Images/OutliningIndicators/InBlock.gif)
bool
ok
=
true
;
while
(
!
st.empty() )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if
( (
int
)st.size ()
>
1
) ok
=
false
;
![](/Images/OutliningIndicators/InBlock.gif)
int
t
=
st.top ();
st.pop();
![](/Images/OutliningIndicators/InBlock.gif)
re.push_back ( t
+
'
A
'
);
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
i
=
0
; i
<
n;
++
i )
if
( data[i][t]
==
1
&&
exist[i] )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
d[i]
--
;
if
( d[i]
==
0
) st.push (i);
}
}
int
len
=
length();
if
( (
int
)re.size ()
<
len )
return
2
;
//
exit circle
if
(
!
ok )
return
0
;
if
( (
int
)re.size ()
==
n )
return
1
;
![](/Images/OutliningIndicators/InBlock.gif)
return
0
;
}
int
main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
while
( scanf(
"
%d%d
"
,
&
n,
&
m), m
+
n
!=
0
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset( degree,
0
,
sizeof
(degree) );
memset( data,
0
,
sizeof
(data ) );
memset( exist,
false
,
sizeof
(exist) );
![](/Images/OutliningIndicators/InBlock.gif)
bool
isok
=
true
;
bool
determin
=
false
;
getchar();
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
i
=
1
; i
<=
m;
++
i )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
char
a, b;
![](/Images/OutliningIndicators/InBlock.gif)
a
=
getchar();
getchar();
b
=
getchar();
getchar();
![](/Images/OutliningIndicators/InBlock.gif)
exist[a
-
'
A
'
]
=
true
;
exist[b
-
'
A
'
]
=
true
;
![](/Images/OutliningIndicators/InBlock.gif)
if
(
!
determin
&&
isok
&&
(data[a
-
'
A
'
][b
-
'
A
'
]
==
1
||
a
==
b) )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
isok
=
false
;
![](/Images/OutliningIndicators/InBlock.gif)
printf(
"
Inconsistency found after %d relations.\n
"
, i);
}
if
( data[b
-
'
A
'
][a
-
'
A
'
]
==
0
) degree[b
-
'
A
'
]
++
;
data[b
-
'
A
'
][a
-
'
A
'
]
=
1
;
![](/Images/OutliningIndicators/InBlock.gif)
int
type;
if
(
!
determin
&&
isok
&&
(type
=
toplogicalsort()) )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if
( type
==
1
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
determin
=
true
;
printf(
"
Sorted sequence determined after %d relations:
"
, i );
for
( size_t x
=
0
; x
<
re.size ();
++
x )
printf(
"
%c
"
, re[x] );
printf(
"
.\n
"
);
}
else
if
( type
==
2
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
isok
=
false
;
![](/Images/OutliningIndicators/InBlock.gif)
printf(
"
Inconsistency found after %d relations.\n
"
, i);
}
}
}
if
(
!
determin
&&
isok ) printf(
"
Sorted sequence cannot be determined.\n
"
);
}
return
0
;
}
posted on 2008-10-03 01:35
Darren 阅读(217)
评论(0) 编辑 收藏 引用 所属分类:
图论