PAT 1142

题目 ： Maximal Clique

分值 ： 25
难度 ： 中等题
思路 ： 对于他给出的点集合,先判断他是否内部任意两个都是连通的,然后再判断点集以外的点是否
       有和点集以内的都联通的点.
坑点 ：

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
using namespace std;
int data[201][201];
int main() {
    int Nv , Ne ;
    cin >> Nv>> Ne ;
    for(int i = 0 ; i< Ne ; i++)
    {
        int c1 , c2 ;
        cin >> c1 >>c2 ;
        data[c1][c2] = data[c2][c1] =1 ;
    }
    int K ;
    cin >> K;
    //cout <<" K" << K <<endl ;
    for(int i = 0 ; i< K ;i++)
    {
        int count ,isclique= 1 , isMaxiaml = 1;
        cin >> count ;
        vector<int> db ;
        vector<int> hash(Nv+1, 0);
        for(int j = 0 ; j < count ; j++)
        {
            int temp=0;
            cin >> temp ;
            hash[temp] =1 ;
            if(isclique)
            {
                for(int ii = 0 ; ii< db.size() ; ii++)
                {
                    if(data[temp][db[ii]] == 0)
                    {
                        //cout << temp <<" "<<db[ii] <<endl ;
                        isclique=0 ;
                        cout <<"Not a Clique"<<endl ;
                        break ;
                    }
                }
            }
            db.push_back(temp);
        }
        if(isclique == 0 ) continue ;
        for(int j = 1 ; j<=Nv ; j ++ )
        {
            if(hash[j] == 0)
            {
                for(int ii = 0 ; ii< db.size() ; ii++)
                {
                    if(data[j][db[ii]] == 0) //和一个点不相连 就不用查了
                        break ;
                    if(ii == db.size()-1 ) //如果j 和db内所有点都相连,显然j可以加入
                        isMaxiaml = 0 ;
                }
            }
        }
        if(isMaxiaml)
            cout <<"Yes"<<endl ;
        else
            cout <<"Not Maximal"<<endl ;
    }
}