AOJ1263

AOJ1263

入力として与えられる隣接行列の対角成分以外は2以上なので、必ずスイッチを経由する。
まず頂点のどれかから辺を伸ばして、スイッチを1つ設置して木のルートと見る。
そうすると、ある頂点からある頂点へ移動するときにそのルートを経由する必要があるかどうかが判定できる。
経由しなくても行ける頂点同士には、ルートから新たに辺を伸ばしてスイッチを設置して同様の処理を繰り返す。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <sstream>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;

typedef long long int lli;

using namespace std;

class DisjointSet{
public:
  vector<int> rank, p;
  DisjointSet(int size){
    rank.resize(size, 0);
    p.resize(size, 0);
  }
  void make(int a){
    rank[a] = 0;
    p[a] = a;
  }
  void join(int a, int b){
    link(find(a), find(b));
  }
  int find(int a){
    return (a == p[a])? a : p[a] = find(p[a]);
  }
  bool isSameSet(int a, int b){
    return find(a) == find(b);
  }
  void link (int a, int b){
    if(rank[a] > rank[b])
      p[b] = a;
    else{
      p[a] = b;
      if(rank[a] == rank[b]) rank[b]++;
    }
  }
};

vector<int> deg;

const int N = 50 + 1;
int g[N][N];

void rec(vector<int> v, vector<int> cost)
{
  DisjointSet ds(N);
  for (int i = 0; i < (int)v.size(); ++i) {
    ds.make(v[i]);
  }

  for (int i = 0; i < (int)v.size(); ++i) {
    int n = v[i];
    for (int j = i + 1; j < (int)v.size(); ++j) {
      int m = v[j];
      if (g[n][m] != cost[i] + cost[j]) {
        ds.join(n, m);
      }
    }
  }

  map<int, int> next;
  for (int i = 0, j = 0; i < (int)v.size(); ++i) {
    int n = ds.find(v[i]);
    if (next.count(n)) ; else next[n] = j++;
  }

  vector<int> u[next.size()];
  vector<int> c[next.size()];

  for (int i = 0; i < (int)v.size(); ++i) {
    int n = ds.find(v[i]);
    u[next[n]].push_back(v[i]);
    c[next[n]].push_back(cost[i] - 1);
  }

  for (int i = 0; i < (int)next.size(); ++i) {
    if (u[i].size() == 1 && c[i][0] == 0) ;
    else rec(u[i], c[i]);
  }

  deg.push_back(next.size() + 1);
  return ;
}

int main(int argc, char *argv[])
{
  int n;
  while (cin >> n && n) {

    deg.clear();

    for (int i = 0; i < (int)n; ++i) {
      for (int j = 0; j < (int)n; ++j) {
        cin >> g[i][j];
      }
    }

    vector<int> v;
    vector<int> cost;
    v.push_back(0);
    cost.push_back(1);
    for (int i = 1; i < (int)n; ++i) {
      v.push_back(i);
      cost.push_back(g[0][i] - 1);
    }

    rec(v, cost);
    --deg.back();

    sort(deg.begin(), deg.end());
    for (int i = 0; i < (int)deg.size(); ++i) {
      if (i) cout << ' ';
      cout << deg[i] ;
    }
    cout << endl;
  }
  return 0;
}