记录编号	192253	评测结果	AAAAAAAA
题目名称	[ZOJ 1015]渔网	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.530 s
提交时间	2015-10-10 11:40:04	内存使用	1.86 MiB

#include<cstdio>
#include<deque>
#include<cstring>
#include<iostream>
#include<iomanip>
#include<set>
#include<algorithm>
using namespace std;
const int SIZEN=1010;
int N,M;
bool g[SIZEN][SIZEN]={0};
int label[SIZEN],dist[SIZEN];
deque<int> s[SIZEN];
set<pair<int,int> > c;
class miku
{
public:
	int id,val;
}P[SIZEN];
bool cmp(miku a,miku b){	return a.val<b.val;}
bool read()
{
	scanf("%d%d",&N,&M);
	if(N==0&&M==0) return 0;
	int fr,to;
	for(int i=1;i<=N;i++) s[i].clear();
	for(int i=1;i<=M;i++) 
	{
		scanf("%d%d",&fr,&to);
		s[fr].push_back(to);
		s[to].push_back(fr);
	}
	return 1;
}
void push(int x)
{
	for(int i=0;i<s[x].size();i++)
	{
		if(label[s[x][i]]!=0) continue;
		c.erase(c.find(make_pair(dist[s[x][i]],s[x][i])));
		dist[s[x][i]]++;
		c.insert(make_pair(dist[s[x][i]],s[x][i]));
	}
}
bool pan()
{
	for(int i=1;i<=N;i++)
	{
		int x=P[i].id;
		bool flag=0;
		int y=0;
		for(int j=i+1;j<=N;j++)
		{
			int z=P[j].id;
			if(!g[x][z]) continue;
			if(!flag) {y=z;flag=1;}
			else if(!g[y][z]) return 0;
		}
	}
	return 1;
}
void work()
{
	memset(label,0,sizeof(label));
	memset(dist,0,sizeof(dist));
	memset(g,0,sizeof(g));
	set<pair<int,int> >::iterator it;
	c.clear();
	for(int i=1;i<=N;i++) c.insert(make_pair(dist[i],i));
	for(int i=N;i>=1;i--)
	{
		it=c.end();it--;
		while(label[it->second]!=0) it--;
		int now=it->second;
		label[now]=i;
		push(now);
	}//这样就get到了消除序列
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<s[i].size();j++) g[i][s[i][j]]=g[s[i][j]][i]=1;
		P[i].id=i;
		P[i].val=label[i];
	}
	sort(P+1,P+1+N,cmp);
	if(pan()) printf("Perfect\n");
	else printf("Imperfect\n");
	printf("\n");
}
int main()
{
	freopen("fishnet.in","r",stdin);
	freopen("fishnet.out","w",stdout);
	while(read()) work();
	return 0;
}