做題思路：
1 弦圖，看了一個(gè)周末有木有！太弱了點(diǎn)，算法完全按照CDQ的PPT上給的最大勢(shì)算法（MCS）求完美消除序列。前前后后sumbit了19次，為WA提供了大量分母啊。。。。多寫(xiě)點(diǎn)為自己備份吧。
2 有用的資料：
3 定理：一個(gè)圖是弦圖當(dāng)且僅當(dāng)它有一個(gè)完美消除序列。所以要先搞到完美消除序列：

4 如何判斷搞到的是不是完美消除序列：

貼代碼：(V*V的復(fù)雜度。。。)

復(fù)制代碼代碼如下:

 
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
const int maxn=1000+10; 
int gra[maxn][maxn]; 
int n, m; 
int label[maxn], temp[maxn], num[maxn]; 
void numberVertex() 
{ 
int i, j; 
//label[n]=0, num[n]=1; 
for(i=n; i>=1; i--) 
{ 
int mm=-1, pos; 
for(j=1; j<=n; j++) 
{ 
if( !num[j] && label[j]>mm) 
{ 
mm=label[j]; 
pos=j; 
} 
} 
num[pos]=i; 
for(j=1; j<=n; j++) 
{ 
if( !num[j] && ( gra[pos][j] || gra[j][pos] ) ) 
label[j]++; 
} 
} 
return ; 
} 
int check() 
{ 
int i, j, flag=1; 
for(i=1; i<=n && flag; i++) 
{ 
memset(temp,0,sizeof(temp)); 
int len=0; 
for(j=1; j<=n; j++) 
{ 
if( num[i]<num[j] && gra[ i ][ j ] ) 
{ 
temp[len++]=j; 
} 
} 
for(j=1; j<len; j++)//在此WA了一天有木有。。。 
if(num[ temp[0] ]>num[ temp[j] ]) 
swap(temp[0], temp[j]); 
for(j=1; j<len; j++) 
if( !gra[ temp[0] ][ temp[j] ] ) 
{ 
flag=0; 
break; 
} 
} 
return flag; 
} 
int main() 
{ 
while( scanf("%d %d",&n,&m)!=EOF ) 
{ 
if(n==0 && m==0) 
break; 
memset(label,0,sizeof(label)); 
memset(num,0,sizeof(num)); 
memset(gra,0,sizeof(gra)); 
for(int i=0; i<m; i++) 
{ 
int x, y; 
scanf("%d %d",&x, &y); 
gra[x][y]=gra[y][x]=1; 
} 
numberVertex(); 
if( check() ) 
puts("Perfect\n"); 
else 
puts("Imperfect\n"); 
} 
return 0; 
} 

相關(guān)文章

C++中的重載、覆蓋、隱藏介紹
這篇文章主要介紹了C++中的重載、覆蓋、隱藏介紹,需要的朋友可以參考下
2015-04-04
簡(jiǎn)單了解設(shè)計(jì)模式中的裝飾者模式及C++版代碼實(shí)現(xiàn)
這篇文章主要介紹了簡(jiǎn)單了解設(shè)計(jì)模式中的裝飾者模式及C++版代碼實(shí)現(xiàn),ConcreteComponent的引用(指針)也可以達(dá)到修飾的功能,需要的朋友可以參考下
2016-03-03
C++實(shí)現(xiàn)聊天程序
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)類(lèi)似QQ聊天程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2021-07-07
C++ Array容器的顯示和隱式實(shí)例化詳細(xì)介紹
這篇文章主要介紹了C++中Array容器的隱式實(shí)例化和顯式實(shí)例化，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧
2022-10-10
C++ Custom Control控件向父窗體發(fā)送對(duì)應(yīng)的消息
這篇文章主要介紹了C++ Custom Control控件向父窗體發(fā)送對(duì)應(yīng)的消息的相關(guān)資料,需要的朋友可以參考下
2015-06-06
C++代碼實(shí)現(xiàn)鏈隊(duì)列詳解
下面小編就為大家分享一篇C++代碼實(shí)現(xiàn)鏈隊(duì)列的示例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧，希望能夠給你帶來(lái)幫助
2021-09-09
C++中唯一三元運(yùn)算符？：實(shí)例詳解
這篇文章主要給大家介紹了關(guān)于C++中唯一三元運(yùn)算符？：的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2021-03-03
解析C語(yǔ)言中結(jié)構(gòu)體struct的對(duì)齊問(wèn)題
這篇文章主要介紹了C語(yǔ)言中結(jié)構(gòu)體struct的對(duì)齊問(wèn)題,作者深入到內(nèi)存分配方面來(lái)進(jìn)行解析,需要的朋友可以參考下
2016-04-04
深入淺出理解C語(yǔ)言初識(shí)結(jié)構(gòu)體
C?數(shù)組允許定義可存儲(chǔ)相同類(lèi)型數(shù)據(jù)項(xiàng)的變量，結(jié)構(gòu)是?C?編程中另一種用戶(hù)自定義的可用的數(shù)據(jù)類(lèi)型，它允許你存儲(chǔ)不同類(lèi)型的數(shù)據(jù)項(xiàng)，本篇讓我們來(lái)了解C?的結(jié)構(gòu)體
2022-02-02
C++實(shí)現(xiàn)LeetCode(160.求兩個(gè)鏈表的交點(diǎn))
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(160.求兩個(gè)鏈表的交點(diǎn)),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-07-07