弦图判定
代码
1 #include<cstdio> 2 #include<queue> 3 #define mp make_pair 4 #define fi first 5 #define sc second 6 using namespace std; 7 const int N = 2001010; 8 int n,m,a,b,i,j; 9 int dp,p[N],pre[N],tt[N],o,vis[N],sum[N],id[N],ID[N]; 10 priority_queue<pair<int,int> > Q; 11 void link(int x,int y) 12 { 13 dp++;pre[dp]=p[x];p[x]=dp;tt[dp]=y; 14 } 15 int main() 16 { 17 scanf("%d%d",&n,&m); 18 for (i=1;i<=m;i++) 19 { 20 scanf("%d%d",&a,&b); 21 link(a,b); 22 link(b,a); 23 } 24 for (i=1;i<=n;i++) 25 Q.push(mp(0,i)); 26 o=n; 27 while (!Q.empty()) 28 { 29 int x=Q.top().fi; 30 int y=Q.top().sc; 31 Q.pop(); 32 if (vis[y]) continue; 33 if (x<sum[y]) continue; 34 ID[y]=o; 35 id[o--]=y; 36 vis[y]=1; 37 i=p[y]; 38 while (i) 39 { 40 if (!vis[tt[i]]) 41 { 42 sum[tt[i]]++; 43 Q.push(mp(sum[tt[i]],tt[i])); 44 } 45 i=pre[i]; 46 } 47 } 48 for (i=1;i<=n;i++) vis[i]=0; 49 50 for (j=1;j<=n;j++) 51 { 52 int x=id[j],cnt1=0,cnt2=0,mi=0x37373737,y=0; 53 i=p[x]; 54 while (i) 55 { 56 if (ID[tt[i]]>j) 57 { 58 if (ID[tt[i]]<mi) mi=ID[tt[i]],y=tt[i]; 59 vis[tt[i]]=1;cnt1++; 60 } 61 i=pre[i]; 62 } 63 64 if (y) 65 { 66 i=p[y]; 67 while (i) 68 { 69 if (vis[tt[i]]) cnt2++; 70 i=pre[i]; 71 } 72 } 73 if ((cnt1!=cnt2+1)&&(y)) 74 { 75 printf("Imperfect"); 76 return 0; 77 } 78 i=p[x]; 79 while (i) 80 { 81 vis[tt[i]]=0; 82 i=pre[i]; 83 } 84 } 85 printf("Perfect"); 86 }