zoj 1015 Fishing Net

题意：
判断任意大于3个点所围成的环中，是否存在两个不相邻的点直接有连线

ac代码如下：
用的是msc，我的代码理解放在代码块里了

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1010;
int graph[maxn][maxn], label[maxn], a[maxn], vis[maxn];
int main() {
	int n, m, o, d, flag;
	while (cin >> n >> m && n && m) {
		flag = 1;
		memset(graph, 0, sizeof(graph));
		memset(label, 0, sizeof(label));
		memset(vis, 0, sizeof(vis));
		for (int i = 1; i <= m; i++) {
			cin >> o >> d;
			graph[o][d] = 1;
			graph[d][o] = 1;
		}

		//这个for使用来计算a[]数组的 也就是求完美消除序列，a[i]就是完美消除数列的第i项
		for (int i = n; i; i--) {
			int k, u = -1;
			//这个for用来找出当前还没访问过的结点中 入度最大的点的索引
			//这个for其实本质就是个贪心算法，因为值最大说明和该点后面那几个点关系最密切，所以方便求完美消除序列
			for (int j = 1; j <= n; j++) {
				if (!vis[j] && u < label[j]) {
					u = label[j];
					k = j;
				}
			}
			a[i] = k;   //标记
			vis[k] = 1; //设置该结点已经被访问过

			//更新label使之 和k有关的点 的入度+1
			for (int j = 1; j <= n; j++) {
				if (graph[k][j])
					label[j]++;
			}
		}

//		for (int i = 1; i <= n; i++) {
//			cout << a[i] << endl;
//		}

		//现在完美消除序列已经求好，只需要检查这个完美消除序列是否合格
		for (int i = 1; i <= n; i++) {
			vector v;
			//这个for用来把和a[i]相连接的结点添加到v中
			for (int j = i + 1; j <= n; j++) {
				if (graph[a[i]][a[j]]) v.push_back(a[j]);
			}
			//这是优化后的检查,检查他们和a[i]是否可以构成一个团
			for (int j = 1; j < v.size(); j++) {
				if (!graph[v[0]][v[j]]) flag = 0;
			}
		}

		if (flag) {
			cout << "Perfect" << endl;
		} else {
			cout << "Imperfect" << endl;
		}
		
		cout << endl;

	}
}

zoj 1015 Fishing Net

C/C++/C#相关栏目本月热门文章