test/yosupo/maximum_independent_set.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 15:54:11+09:00
• Problem: https://judge.yosupo.jp/problem/maximum_independent_set

Depends on

• graph/independentset.cpp

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/maximum_independent_set

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../graph/independentset.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  IndependentSet G(n);
  for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    G.add_edge(u,v);
  }
  int X=G.build();
  cout<<X<<endl;
  for(int i=0;i<X;i++){
    if(i) cout<<" ";
    cout<<G.ans[i];
  }
  cout<<endl;
  return 0;
}

#line 1 "test/yosupo/maximum_independent_set.test.cpp"
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/maximum_independent_set

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "graph/independentset.cpp"

#line 3 "graph/independentset.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
struct IndependentSet{
  int n;
  vector<int> deg,used,dead,pre,ans;
  vector<vector<int> > G;

  IndependentSet(int n):
    n(n),deg(n),used(n,0),dead(n,0),G(n){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  int res,cnt,alive;
  void dfs(){
    if(cnt+alive<=res) return;

    int v=-1;
    for(int i=0;i<n;i++){
      if(used[i] or dead[i]) continue;
      if(deg[i]<=1){
        v=i;
        break;
      }
      if(v<0 or deg[v]<deg[i]) v=i;
    }
    if(v<0) return;

    if(deg[v]!=1){
      dead[v]=1;
      alive--;
      for(int u:G[v]) deg[u]--;

      dfs();

      dead[v]=0;
      alive++;
      for(int u:G[v]) deg[u]++;
    }
    {
      used[v]=1;
      alive--;
      for(int u:G[v])
        if(0==dead[u]++) alive-=!used[u];
      cnt++;
      if(res<cnt) pre=used;
      res=max(res,cnt);

      dfs();

      used[v]=0;
      alive++;
      for(int u:G[v])
        if(--dead[u]==0) alive+=!used[u];
      cnt--;
    }
  }

  int build(){
    for(int i=0;i<n;i++) deg[i]=G[i].size();
    res=0,cnt=0,alive=n;
    dfs();
    for(int i=0;i<n;i++)
      if(pre[i]) ans.emplace_back(i);
    return res;
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 8 "test/yosupo/maximum_independent_set.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  IndependentSet G(n);
  for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    G.add_edge(u,v);
  }
  int X=G.build();
  cout<<X<<endl;
  for(int i=0;i<X;i++){
    if(i) cout<<" ";
    cout<<G.ans[i];
  }
  cout<<endl;
  return 0;
}

Back to top page