ZOJ 1015 Fishing Net（弦图判定）

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=15

题意：

判断是否是弦图。

思路：

所谓弦图，也就是对于一个无向图，若该图的任意一个长度大于3的环中存在一条边连接这个环上不相邻的两点，则此图称作弦图。

弦图的判断不难，先用最大势算法计算出完美消除序列，然后用完美消除序列判断原图是否是弦图，如何从完美消除序列判断原图是不是弦图？最朴素的办法是依次判断 {vi+1,…,vn}中所有与vi相邻的点是否构成了一个团。可以这样优化：设{vi+1,…,vn}中所有与vi相邻的点依次为 vj1,……,vjk。只需判断vj1是否与vj2,……,vjk相邻即可。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<sstream>
 6 #include<vector>
 7 #include<stack>
 8 #include<queue>
 9 #include<cmath>
10 #include<map>
11 #include<set>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,ll> pll;
15 const int INF = 0x3f3f3f3f;
16 const int maxn=1000+5;
17 
18 int n, m;
19 int tot;
20 int head[maxn];
21 int label[maxn]; //label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号
22 int vis[maxn];
23 int q[maxn];
24 int mp[maxn][maxn];
25 
26 struct node
27 {
28     int v;
29     int next;
30 }e[maxn*maxn+5];
31 
32 void addEdge(int u, int v)
33 {
34     e[tot].v=v;
35     e[tot].next=head[u];
36     head[u]=tot++;
37 }
38 
39 void MCS()  //最大势算法
40 {
41     memset(vis,0,sizeof(vis));
42     memset(label,0,sizeof(label));
43     for(int i=n;i;i--)
44     {
45         int pos=0;
46         for(int j=1;j<=n;j++)   //选择当前未访问且label值最大的
47             if(!vis[j] && label[j]>=label[pos])   pos=j;
48         vis[pos]=1;
49         q[i]=pos;
50         for(int j=head[pos];j!=-1;j=e[j].next)  //与pos结点相邻的结点label值+1
51             label[e[j].v]++;
52     }
53 }
54 
55 bool check()
56 {
57     for(int i=1;i<=n;i++)
58     {
59         vector<int> v;
60         for(int j=i+1;j<=n;j++)
61             if(mp[q[i]][q[j]]==1)  v.push_back(q[j]);
62         for(int j=1;j<v.size();j++)
63             if(mp[v[0]][v[j]]==0)  return false;
64     }
65     return true;
66 }
67 
68 int main()
69 {
70     //freopen("in.txt","r",stdin);
71     while(scanf("%d%d",&n,&m)!=EOF)
72     {
73         if(n==0 && m==0)  break;
74         tot=0;
75         memset(head,-1,sizeof(head));
76         memset(mp,0,sizeof(mp));
77         while(m--)
78         {
79             int u,v;
80             scanf("%d%d",&u,&v);
81             addEdge(u,v);
82             addEdge(v,u);
83             mp[u][v]=mp[v][u]=1;
84         }
85         MCS();
86         if(check()==true) puts("Perfect
");
87         else puts("Imperfect
");
88     }
89     return 0;
90 }