Posted on 2008-08-11 20:59
Hero 阅读(105)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
/*
ID: wangzha4
LANG: C++
TASK: race3
*/
/*
Test 1: TEST OK [0.000 secs, 2732 KB]
Test 2: TEST OK [0.000 secs, 2728 KB]
Test 3: TEST OK [0.011 secs, 2728 KB]
Test 4: TEST OK [0.011 secs, 2728 KB]
Test 5: TEST OK [0.011 secs, 2728 KB]
Test 6: TEST OK [0.011 secs, 2728 KB]
Test 7: TEST OK [0.022 secs, 2732 KB]
Test 8: TEST OK [0.011 secs, 2728 KB]
Test 9: TEST OK [0.011 secs, 2728 KB]
Test 10: TEST OK [0.011 secs, 2728 KB]
Test 11: TEST OK [0.011 secs, 2728 KB]
*/
//ques1 :-- 直接枚举点，删除，然后判断能否从起点到终点
//ques2 :-- 从ques1中的结果集out1[]中枚举点，从起点到该点遍历一遍，
// 然后从该点到终点遍历一遍，看是否有重复遍历的点
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#define llong unsigned long long
#define unint unsigned int
#define printline printf( "\n" )
typedef long long huge ;
const int Base=1000000000;
const int Capacity=100;
const int INF = 1000000 ;
const int size = 60 ;
int edge[size][size] = {0} ;
int inn ;//the max node
int out1[size] = {0} ;
int out2[size] = {0} ;
int flag[size] = {0} ;
int flag2[size] = {0} ;
bool hasfind ;
void input()
{
int inval ;
for( inn=0; ; inn++ )
{
scanf( "%d", &inval ) ; if( -1 == inval ) break ;
if( -2 == inval ) continue ;
edge[inn][inval] = 1 ;
while( scanf( "%d",&inval ) != EOF && inval != -2 )
edge[inn][inval] = 1 ;
}
inn -- ;
//printf( "inn==%d\n", inn ) ;
}
void DFS1( int sn, int en )
{
if( sn == en ) { hasfind = true ; return ; }
flag[sn] = 1 ;
for( int i=0; i<=inn; i++ )
{
if( 0==flag[i] && edge[sn][i] )
{
DFS1( i, en ) ;
}
}
}
void deal_ques1()
{
int copyedgein[size] ; int copyedgeout[size] ;
for( int i=1; i<inn; i++ )
{//删除一个node,看能否从起点到达终点
memset( flag, 0, sizeof(flag) ) ;
for( int j=0; j<=inn; j++ )
{
copyedgein[j] = edge[i][j] ;
edge[i][j] = 0 ;
}
for( int j=0; j<=inn; j++ )
{
copyedgeout[j] = edge[j][i] ;
edge[j][i] = 0 ;
}
hasfind = false ;
DFS1( 0, inn ) ;
if( !hasfind ) out1[++out1[0]] = i ;
for( int j=0; j<=inn; j++ ) edge[i][j] = copyedgein[j] ;
for( int j=0; j<=inn; j++ ) edge[j][i] = copyedgeout[j] ;
}
}
void DFS2( int sn, int en )
{
flag2[sn] = 1 ;
for( int i=0; i<=inn; i++ )
if( edge[sn][i] && 0==flag2[i] ) DFS2( i, en ) ;
}
void deal_ques2()
{
for( int i=1; i<=out1[0]; i++ )
{
memset( flag, 0, sizeof(flag) ) ;
memset( flag2, 0, sizeof(flag2) ) ;
int delnode = out1[i] ;
DFS2( delnode, inn ) ;
DFS1( 0, delnode ) ;
bool iskey = true ;
for( int k=0; k<=inn; k++ )
{
if( flag[k]==1 && flag2[k]==1 )
{ iskey = false ; break ; }
}
if( iskey ) out2[++out2[0]] = delnode ;
}
}
void process()
{
deal_ques1() ;
deal_ques2() ;
}
int cmp( const void *a, const void *b )
{
return *(int *)a - *(int *)b ;
}
void output()
{
qsort( out1+1, out1[0], sizeof(out1[1]), cmp ) ;
printf( "%d", out1[0] ) ;
for( int i=1; i<=out1[0]; i++ )
printf( " %d", out1[i] ) ;
printf( "\n" ) ;
qsort( out2+1, out2[0], sizeof(out2[1]), cmp ) ;
printf( "%d", out2[0] ) ;
for( int i=1; i<=out2[0]; i++ )
printf( " %d", out2[i] ) ;
printf( "\n" ) ;
}
int main()
{
//freopen( "race3.in", "r", stdin ) ;
//freopen( "race3.out","w",stdout ) ;
input() ;
process() ;
output() ;
return 0 ;
}