1015_fishing_net.cpp

来自「ACM比赛解题报告,包括hdu1880、zoj1010、zoj1015」· C++ 代码 · 共 107 行

#include<iostream>
#include<vector>
using namespace std;

const int MAX = 1005;

enum COLOR{ WHITE, GRAY, BLACK };
struct Vertex
{
	COLOR color;
	int pre;
};
Vertex vList[ MAX ];

vector<int> adjList[ MAX ];
int N, M;
bool find3;

void read();
bool findCycle();
void dfs( int vertex );

int main()
{
	while ( scanf( "%d %d", &N, &M ) != EOF && N && M )
	{
		read();
		
		if ( N <= 3 )
			puts( "Perfect" );
		else if ( findCycle() )
			puts( "Imperfect" );
		else
			puts( "Perfect" );
		
		putchar( '\n' );
	}
	
	return 0;
}

void read()
{
	int i, u, v;
	for ( i = 1; i <= N; i ++ )
		adjList[ i ].clear();
	
	for ( i = 1; i <= M; i ++ )
	{
		scanf( "%d %d", &u, &v );
		adjList[ u ].push_back( v );
		if ( u != v )
			adjList[ v ].push_back( u );
	}
}

bool findCycle()
{
	int i;
	for ( i = 1; i <= N; i ++ )
		vList[ i ].color = WHITE;
	
	find3 = false;
	
	for ( i = 1; i <= N && !find3; i ++ )
		if ( vList[ i ].color == WHITE )
			dfs( i );
		
	
	return find3;
}

bool greaterThan3( int pre, int cur )
{
	for ( int i = 0; i < adjList[ pre ].size(); i ++ )
		if ( adjList[ pre ][ i ] == cur )
			return false;
		
	return true;
}

void dfs( int vertex )
{
	if ( find3 )
		return;
	
	vList[ vertex ].color = GRAY;
	
	int i;
	for ( i = 0; i < adjList[ vertex ].size() && !find3; i ++ )
	{
		int cur = adjList[ vertex ][ i ];
		if ( vList[ cur ].color == WHITE )
		{
			vList[ cur ].pre = vertex;
			dfs( cur );
		}
		else if ( vList[ cur ].color == GRAY && vList[ vertex ].pre != cur && vertex != cur )
		{
			if ( greaterThan3( vList[ vertex ].pre, cur ) )
				find3 = true;
		}
	}
	
	vList[ vertex ].color = BLACK;
}