test/aoj/2948.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 15:54:11+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2948

Depends on

• graph/independentset.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2948

#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;
  while(cin>>n>>m,n){
    vector< vector<int> > as(n,vector<int>(m));
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
        cin>>as[i][j];

    IndependentSet G(m);
    for(int a=0;a<m;a++){
      for(int b=0;b<a;b++){
        int ng=0;
        for(int i=0;i<n;i++){
          for(int j=0;j<i;j++){
            if(as[i][a]==as[j][a]) continue;
            if(as[i][b]==as[j][b]) continue;
            if((as[i][a]>as[j][a])^(as[i][b]>as[j][b])) ng=1;
            if(ng) break;
          }
          if(ng) break;
        }

        if(ng) G.add_edge(a,b);
      }
    }

    cout<<G.build()<<endl;
  }
  return 0;
}

#line 1 "test/aoj/2948.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2948

#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/aoj/2948.test.cpp"
#undef call_from_test

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

  int n,m;
  while(cin>>n>>m,n){
    vector< vector<int> > as(n,vector<int>(m));
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
        cin>>as[i][j];

    IndependentSet G(m);
    for(int a=0;a<m;a++){
      for(int b=0;b<a;b++){
        int ng=0;
        for(int i=0;i<n;i++){
          for(int j=0;j<i;j++){
            if(as[i][a]==as[j][a]) continue;
            if(as[i][b]==as[j][b]) continue;
            if((as[i][a]>as[j][a])^(as[i][b]>as[j][b])) ng=1;
            if(ng) break;
          }
          if(ng) break;
        }

        if(ng) G.add_edge(a,b);
      }
    }

    cout<<G.build()<<endl;
  }
  return 0;
}

Back to top page