信奥赛普及组 P1692 部落卫队（收索与剪枝) 参考代码

#include <bits/stdc++.h>

using namespace std;

const int MN=101;

int out[MN],cur[MN];

int vis[MN];

vector<int> emy[MN];

int hmax,ans;

void search(int k,int n){

    //1 search 选中分支, 要回溯

    if(vis[k]==0){

        vis[k]=1;

        cur[k]=1;

        ans++;

        for(auto v : emy[k]){

            vis[v]++;

        }

        if(k==n){

            if(ans>hmax){

                for(int i=1;i<=n;i++){

                    out[i]=cur[i];

                }

                hmax=ans;

            }

        }else{    

            search(k+1,n);

        }    

        for(auto v : emy[k]){

            vis[v]--;

        }

        cur[k]=0;

        ans--;

        vis[k]=0;

    }

    //2 search 未选中分支, 不用回溯

    if(k==n){

        if(ans>hmax){

            for(int i=1;i<=n;i++){

                out[i]=cur[i];

            }

            hmax=ans;

        }

    }else{    

        search(k+1,n);

    }

        

}    

int main()

{

    int n,m;

    cin>>n>>m;

    for(int i=0;i<m;i++){

        int a,b;

        cin>>a>>b;

        emy[a].push_back(b);

        emy[b].push_back(a);

    }

    search(1,n);

    cout<<hmax<<endl;

    for(int i=1;i<=n;i++){

        cout<<out[i]<<" ";

    }

    cout<<endl;

    return 0;

}