题目大意:
题解:
今天刚学了《弦图与区间图》
本来写了一个60行+的学习笔记
结果因为忘了保存重启电脑后被还原了...
那就算了吧.
MCS最大势算法,写起来挺愉悦的.
不过觉得除了做裸题就只能做裸题了..
直接贴板子
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;static char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 1024;
const int maxm = maxn*maxn;
struct Edge{
int next,to;
}G[maxm];
int head[maxn],cnt;
void add(int u,int v){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
}
vector<int>ws[maxn];
int seq[maxn],lab[maxn],pos[maxn];
bool map[maxn][maxn];
int main(){
int n,m;read(n);read(m);
int u,v;
rep(i,1,m){
read(u);read(v);
map[u][v] = map[v][u] = true;
add(u,v);add(v,u);
}
rep(i,1,n) ws[0].push_back(i);
int nw = 0;
per(i,n,1){
while(1){
u = ws[nw].back();
if(pos[u]) ws[nw].pop_back();
else break;
while(ws[nw].empty()) -- nw;
}
pos[u] = i;seq[i] = u;
for(int p = head[u];p;p=G[p].next){
++ lab[G[p].to];
nw = max(nw,lab[G[p].to]);
ws[lab[G[p].to]].push_back(G[p].to);
}
}
bool flag = false;
per(i,n,1){
u = seq[i];
v = -1;
for(int i = head[u];i;i=G[i].next){
if(pos[G[i].to] < pos[u]) continue;
if(v == -1 || (pos[v] > pos[G[i].to])) v = G[i].to;
}
for(int i = head[u];i;i=G[i].next){
if(pos[G[i].to] < pos[u]) continue;
if(v != G[i].to && !map[v][G[i].to]){
flag = true;
break;
}
}
if(flag) break;
}
puts(flag ? "Imperfect" : "Perfect");
return 0;
}