题面
Vjudge
Sol
给出一个n个点的无向图，询问是否为弦图
做法见上上上篇博客
# include <bits/stdc++.h># define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;const int _(1005);typedef long long ll;IL int Input(){ ???RG int x = 0, z = 1; RG char c = getchar(); ???for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1; ???for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); ???return x * z;}int n, m, first[_], cnt, label[_], vis[_], best, Q[_], id[_], S[_];struct Edge{ ???int to, next;} edge[_ * _];vector <int> P[_];IL void Add(RG int u, RG int v){ ???edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++;}IL int Check(){ ???for(RG int i = 1; i <= n; ++i) vis[i] = 0; ???for(RG int i = n; i; --i){ ???????RG int ret = 1; S[0] = 0; ???????for(RG int e = first[Q[i]]; e != -1; e = edge[e].next) ???????????if(id[edge[e].to] > i) vis[S[++S[0]] = edge[e].to] = 1; ???????for(RG int e = first[S[1]]; e != -1; e = edge[e].next) ???????????if(edge[e].to != S[1] && vis[edge[e].to]) ???????????????ret += (vis[edge[e].to] == 1), ++vis[edge[e].to]; ???????for(RG int j = 1; j <= S[0]; ++j) vis[S[j]] = 0; ???????if(S[0] && ret != S[0]) return 0; ???} ???return 1;}int main(RG int argc, RG char* argv[]){ ???while(233){ ???????n = Input(), m = Input(); ???????if(!n && !m) break; ???????cnt = best = 0; ???????for(RG int i = 1; i <= n; ++i) P[i].clear(), first[i] = -1, vis[i] = label[i] = 0; ???????for(RG int i = 1; i <= m; ++i){ ???????????RG int u = Input(), v = Input(); ???????????Add(u, v), Add(v, u); ???????} ???????for(RG int i = 1; i <= n; ++i) P[0].push_back(i); ???????for(RG int i = n, nw; i; --i){ ???????????for(RG int flg = 0; !flg; ){ ???????????????for(RG int j = P[best].size() - 1; ~j; --j) ???????????????????if(vis[P[best][j]]) P[best].pop_back(); ???????????????????else{ ???????????????????????nw = P[best][j], flg = 1; ???????????????????????break; ???????????????????} ???????????????if(!flg) --best; ???????????} ???????????vis[nw] = 1, Q[i] = nw, id[nw] = i; ???????????for(RG int e = first[nw]; e != -1; e = edge[e].next) ???????????????if(!vis[edge[e].to]){ ???????????????????P[++label[edge[e].to]].push_back(edge[e].to); ???????????????????best = max(best, label[edge[e].to]); ???????????????} ???????} ???????Check() ? puts("Perfect") : puts("Imperfect"); ???????puts(""); ???} ???return 0;}