c++ - 使用给定的节点数和不相邻边列表查找最大团

Question

上周我一直在努力解决一个任务。这让我疯狂。任务是:

给定节点数 N(1 <= N <= 10`000)，

非相邻节点对计数 M(1 <= M <= 200`000)

和非相邻节点自身配对

M_0A, M_0B,

M_1A, M_1B,

...

M_M-1A, M_M-1B,

找到最大团。

我目前正在尝试各种 bron-kerbosch 算法变体。但是每次我在测试站点上都有时间限制。我发布了唯一没有时间限制但答案错误的代码。通过不在每次递归时都创建一个新集合来优化代码。

无论如何，请帮助我。我是一个绝望的拉脱维亚青少年程序员。我知道这个问题是可以解决的，因为在测试现场已经有很多人解决了。

#include <set>
#include <vector>

std::map<int, std::set<int> > NotAdjacent;

unsigned int MaxCliqueSize = 0;

void PrintSet(std::set<int> &s){
    for(auto it = s.begin(); it!=s.end(); it++){
        printf("%d ",*it);
    }
    printf("\n");
}

void Check(std::set<int> &clique, std::set<int> &left){
    //printf("printing clique: \n");
    //PrintSet(clique);
    //printf("printing left: \n");
    //PrintSet(left);

    if(left.empty()){
        //PrintSet(clique);
        if(clique.size()>MaxCliqueSize){
            MaxCliqueSize = clique.size();
        }
        return;
    }


    while(left.empty()==false){
        std::vector<int> removed;

        int v = *left.begin();
        left.erase(left.begin());


        for(auto it2=NotAdjacent[v].begin();it2!=NotAdjacent[v].end();it2++){

            auto findResult = left.find(*it2);

            if(findResult!=left.end()){
                removed.push_back(*it2);
                left.erase(findResult);
            }

        }

        clique.insert(v);
        Check(clique, left);
        clique.erase(v);

        for(unsigned int i=0;i<removed.size();i++){
            left.insert(removed[i]);
        }

    }
}

int main(){
    int n, m;
    scanf("%d%d",&n,&m);

    int a, b;
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        NotAdjacent[a].insert(b);
        NotAdjacent[b].insert(a);
    }

    std::set<int> clique, left;

    for(int i=1;i<=n;i++){
        left.insert(i);
    }
    Check(clique, left);
    printf("%d",MaxCliqueSize);
}

Answer 1

就其值(value)而言，这段代码似乎通过了 5 次测试，我认为所有其他代码都超过了时间或内存限制(作为 C++11 提交)。这个想法是在图补中找到一个最大独立集，我们很容易收到它的边。该算法是我能理解的标准贪婪算法。也许这可以给你或其他人更多的想法？我相信 MIS 有一些改进的算法。

#include <iostream>
using namespace std;

#include <map>
#include <set>
#include <vector>
#include <algorithm>

std::map<int, std::set<int> > NotAdjacent;
vector<int> Order;
unsigned int NumConnectedToAll = 0;
unsigned int MaxCliqueSize = 0;

bool sortbyN(int a, int b){ 
  return (NotAdjacent[a].size() > NotAdjacent[b].size());
}  

void mis(std::set<int> &g, unsigned int i, unsigned int size){
    if (g.empty() || i == Order.size()){
        if (size + NumConnectedToAll > MaxCliqueSize)
          MaxCliqueSize = size + NumConnectedToAll;
        return;
    }

    if (g.size() + size + NumConnectedToAll <= MaxCliqueSize)
     return;

    while (i < Order.size() && g.find(Order[i]) == g.end())
      i++;
    int v = Order[i];
    std::set<int> _g;
    _g = g;
    _g.erase(v);
    for (auto elem : NotAdjacent[v])
      _g.erase(elem);

    mis(_g, i + 1, size + 1);
}

int main(){
    int n, m;
    scanf("%d%d",&n,&m);

    int a, b;
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        NotAdjacent[a].insert(b);
        NotAdjacent[b].insert(a);
    }

    std::set<int> g;
    Order.reserve(NotAdjacent.size());
    for (auto const& imap: NotAdjacent){
      Order.push_back(imap.first);
      g.insert(imap.first);
    }
    sort(Order.begin(), Order.end(), sortbyN); 

    for (int i=1; i<=n; i++)
      if (NotAdjacent.find(i) == NotAdjacent.end())
        NumConnectedToAll++;

    for (unsigned int i=0; i<Order.size(); i++){
      mis(g, i, 0);
      g.erase(Order[i]);
    }

    printf ("%d", MaxCliqueSize);
    return 0;
}