? ? ? ? ? ? ? ? ? ?ZOJ1015

題意簡述：給定一個無向圖，判斷是否存在一個長度大于3的環路，且其上沒有弦（連接環上不同兩點的邊且不在環上）。

命題等價于該圖是否存在完美消除序列。

所謂完美消除序列：在 vi,vi+1,...vn vi與之后與vi相鄰的點構成一個團（完全子圖）。

求完美消除序列的MCS算法。倒序給點標號，標號為i的點出現在序列的第i項。對每個頂點i，維護標號label[i]，表示標號的度，每次選擇標號最大的點標號。用堆加速。

?

求出了完美消除序列后，只要判斷這個序列是否合法就可以得出結論。

在 vi,vi+1,...vn的導出子圖中找到與vi相鄰的標號最小（度最小）的點，設為vj，再檢查vj是否與每個vi的鄰接點相鄰。

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<vector> #include<queue> #include<algorithm> #include<set> #define clr(x,y) memset(x,y,sizeof(x)) using namespace std; const int maxn=1010;vector<int> construct(int n,vector<int> adj[maxn]) {static int rank[maxn],label[maxn];clr(rank,-1);clr(label,0);priority_queue<pair<int,int> > heap;for(int i=1;i<=n;i++)heap.push(make_pair(0,i));for(int i=n-1;i>=0;i--){while(true){int u=heap.top().second;heap.pop();if(rank[u]==-1){rank[u]=i;for(vector<int>:: iterator iter=adj[u].begin();iter!=adj[u].end();++iter){if(rank[*iter]==-1){label[*iter]++;heap.push(make_pair(label[*iter],*iter));}}break;}}}vector<int> result(n);for(int i=1;i<=n;i++) {result[rank[i]]=i;} return result; }bool check(int n,vector<int>adj[maxn],vector<int> ord) {static bool mark[maxn];static int rank[maxn];for(int i=0;i<n;i++)rank[ord[i]]=i;clr(mark,0);for(int i=0;i<n;i++){vector<pair<int,int> >tmp;for(vector<int>::iterator iter=adj[ord[i]].begin();iter!=adj[ord[i]].end();++iter)if(!mark[*iter])tmp.push_back(make_pair(rank[*iter],*iter));sort(tmp.begin(),tmp.end());if(tmp.size()){int u=tmp[0].second;set<int> tmpAdj;for(vector<int>::iterator iter=adj[u].begin();iter!=adj[u].end();++iter){tmpAdj.insert(*iter);}for(int i=1;i<(int)tmp.size();++i){if(!tmpAdj.count(tmp[i].second))return false;}}mark[ord[i]]=true; } return true; }bool is_chordal(int nodeCount,vector<pair<int,int> >edges) {int n=nodeCount;vector<int>adj[maxn];for(int i=0;i<=n;i++)adj[i].clear();for(vector<pair<int,int> >::iterator iter=edges.begin();iter!=edges.end();++iter){adj[iter->first].push_back(iter->second);adj[iter->second].push_back(iter->first);} return check(n,adj,construct(n,adj)); }int main() {int n,m;while(scanf("%d%d",&n,&m)){if(n==0&&m==0)return 0;vector<pair<int,int> >ed;for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);ed.push_back(make_pair(a,b));}if(is_chordal(n,ed))printf("Perfect\n\n");else printf("Imperfect\n\n");}return 0; }

　　完美消除序列還有廣泛的應用，以后來補充。

轉載于:https://www.cnblogs.com/heisenberg-/p/6444707.html

總結

以上是生活随笔為你收集整理的无向图的完美消除序列 判断弦图 ZOJ 1015 Fish net的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。