记录编号	151979	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2012] 旅游	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	2.992 s
提交时间	2015-03-12 15:38:43	内存使用	4.89 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============
struct Trangles{
   int p[5];
   bool operator <(const Trangles &rhs) const{
      if (p[1]!=rhs.p[1]) return p[1]<rhs.p[1];
      if (p[2]!=rhs.p[2]) return p[2]<rhs.p[2];
      if (p[3]!=rhs.p[3]) return p[3]<rhs.p[3];
      return false;
   }
   void Make(){
      int &a=p[1],&b=p[2],&c=p[3];
      if (a>b) swap(a,b);
      if (b>c) swap(b,c);
      if (a>b) swap(a,b);
   }
};
///==============var declaration=================
const int MAXN=200050;
int n;
int d[MAXN];
map<pair<int,int>,vector<int> > Mp;
map<Trangles,int> Index;
Trangles city[MAXN];
///==============function declaration============
int BFS(int S);
///==============main code=======================
int main()
{
   freopen("journey.in","r",stdin);
   freopen("journey.out","w",stdout);
   sacnf("%d",&n);
   for(int i=1;i<=n-2;i++){
      scanf("%d%d%d",&city[i].p[1],&city[i].p[2],&city[i].p[3]);
      city[i].Make();
      Mp[make_pair(city[i].p[1],city[i].p[2])].push_back(i);
      Mp[make_pair(city[i].p[1],city[i].p[3])].push_back(i);
      Mp[make_pair(city[i].p[2],city[i].p[3])].push_back(i);
   }
   memset(d,0,sizeof(d));d[1]=1;
   int Far=BFS(1);
   memset(d,0,sizeof(d));d[Far]=1;
   Far=BFS(Far);
   printf("%d\n",d[Far]);
   return 0;
}
///================fuction code====================
int BFS(int S){
   queue <int> Q;Q.push(S);
   while (!Q.empty()){
      int x=Q.front();Q.pop();
      for(int ii=1;ii<=2;ii++)
         for(int jj=ii+1;jj<=3;jj++){
            int a=city[x].p[ii],b=city[x].p[jj];
            int siz=Mp[make_pair(a,b)].size();
            for(int i=0;i<siz;i++){
               int &e=Mp[make_pair(a,b)][i];
               if (d[e]!=0) continue;
               d[e]=d[x]+1;
               Q.push(e);
            }
         }
   }
   int Far=1;
   for(int i=1;i<=n-1;i++)
      if (d[i]>d[Far])
         Far=i;
   return Far;

}