2258 The Settlers of Catan

PKU

http://poj.org/problem?id=2258

概要

グラフが与えられるので最も長いパスの長さを答える。

ソース

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

int maxdepth;
bool used[25][25];

void dfs(int depth,int p,vector<vector<int> > &g) {
  maxdepth = max(depth, maxdepth);
  for(int i=0; i<g[p].size(); ++i) {
    if(used[p][g[p][i]]) continue;
    used[p][g[p][i]] = used[g[p][i]][p] = true;
    dfs(depth+1,g[p][i],g);
    used[p][g[p][i]] = used[g[p][i]][p] = false;
  }
}

int main() {
  int n,m,i,j,k;
  while(scanf("%d %d", &n, &m), n|m) {
    vector<vector<int> > g(n);
    maxdepth = 0;
    rep(i,m) {
      scanf("%d %d", &j, &k);
      g[j].push_back(k);
      g[k].push_back(j);
    }

    int ans = 0;
    rep(i,n) {
      memset(used, false, sizeof(used));
      dfs(0,i,g);
    }
    printf("%d\n", maxdepth);
  }
}