弦图判断.cpp

本人参加ACM竞赛使用的一些算法模板

/********************************************************************
*
*   弦图判定 (zoj 1015	Fishing Net)
*
********************************************************************/
#include <cstdio>
#include <iostream>
using namespace std;
int const MAXN = 1024;
int cnt[MAXN];//点度
int graph[MAXN][MAXN];//邻接表
bool adj[MAXN][MAXN];//邻接矩阵
int N, M;//点数，边数。
bool read_data(){
	scanf("%d %d", &N, &M);
	if(!N && !M){
		return false;
	}
	for (int i = 0; i < N; ++i){
		cnt[i] = 0;
		for (int j = 0; j < N; ++j){
			adj[i][j] = false;
		}
	}
	int u(0), v(0);
	while (M--){
		scanf("%d %d", &u, &v);
		--u;
		--v;
		graph[u][cnt[u]++] = v;
		graph[v][cnt[v]++] = u;
		adj[u][v] = adj[v][u] = true;
	}
	return true;
}
int label[MAXN], number[MAXN], sim[MAXN];
//label记录与之相邻的未标记的节点数目，number为标记，
//sim通过标记反向找出相应节点
void cardy_search(){//找出一个maximun cardinality order
	for (int i = 0; i < N; ++i){//初始所有标记置空。
		label[i] = 0;
		number[i] = -1;
	}
	label[N] = -1;
	for (int i = N - 1; i > -1; --i){
		int v(N);
		for (int j = 0; j < N; ++j){
			//找出一个未标记的且拥有最多相邻未标节点的节点v
			if(number[j] == -1 && label[j] > label[v]){
				v = j;
			}
		}
		number[v] = i;//对v进行标记和反向映射
		sim[i] = v;
		for (int j = 0; j < cnt[v]; ++j){//对v的未标记邻接节点增加label值
			int w = graph[v][j];
			if(number[w] == -1){
				++label[w];
			}
		}
	}
}
bool perfect_order(){
	//判定maximun cardinality order是不是perfect，弦图的充要条件是
	//maximun cardinality order是一个perfect eliminination order
	for (int i = 0; i < N - 1; ++i){
		int v = sim[i];
		int w, m(N);
		for (int j = 0; j < cnt[v]; ++j){
			//取出与v相邻的最小的比v大的标号值
			w = graph[v][j];
			if(number[w] > number[v] && number[w] < m){
				m = number[w];
			}
		}
		m = sim[m];
		for (int j = 0; j < cnt[v]; ++j){
			w = graph[v][j];
			if(number[m] < number[w] && !adj[w][m]){//满足判断条件即非弦图
				return false;
			}
		}
	}
	return true;
}
int main(){
	while (read_data() ){
        cardy_search();
        if(perfect_order() ){
			printf("Perfect\n");
		}
		else{
			printf("Imperfect\n");
		}
		printf("\n");
	}
	return 0;
}