hdu 컴퓨터 대학 대학생 프로 그래 밍 경기 (2015 '11) 1007 유채꽃 왕국

유채꽃 왕국
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1720    Accepted Submission(s): 447
Problem Description
  프로 그래 밍 경연 대 회 를 앞 두 고 학교 ACM 합숙 훈련 팀 의 주축 으로서 샤 오 밍 은 열심히 훈련 해 왔 다.오늘 은 날씨 가 좋 고 코치 님 도 기분 이 아주 좋 습 니 다. 이례 적 으로 선수 들 에 게 하루 를 쉬 게 해 주 었 습 니 다. 샤 오 밍 은 자신의 당 나 귀 를 타고 교외 로 나 가 답청 을 했 습 니 다.
  성 을 나 간 지 얼마 되 지 않 아 샤 오 밍 은 커 다란 유채꽃 을 보고 눈앞 의 아름 다운 경치 의 유혹 을 참 지 못 하고 돌아 들 어 갔다. 누가 생각 했 겠 는가? 이 절 개 는 유채꽃 왕국 에 잘못 들 어 갔다!
  유채꽃 왕국 에는 유채꽃 요정 들 이 많이 살 고 있 는데, 이것 은 피 보 나치 수열 을 특히 사랑 하 는 생물 이다.이 나라 에는 요정 한 마리 가 한 가족 에 속한다.엘 프 가 태 어 났 을 때, 몸 에 코드 가 찍 혀 있 는데, 이 엘 프 의 능력 치 를 나타 낸다. 만약 이 능력 치가 피 보 나치 수열 에 존재 한다 면, 그 는 자신 이 있 는 가족 에 게 약간의 위신 을 더 해 줄 것 이다.샤 오 밍 은 요정 들 과 이 야 기 를 나 누 며 모든 요정 들 의 관 계 를 알 게 되 었 다.
  지금 샤 오 밍 은 유채꽃 왕국 에서 가장 명망 이 높 은 가문 의 위상 이 얼마 인지 알 고 싶 어 합 니 다. 그 를 도와 주 시 겠 습 니까?샤 오 밍 은 요정 들 사이 의 관계 네트워크 를 알려 줄 것 이다. 전체 관계 네트워크 가 너무 커서 샤 오 밍 이 그 중 일 부 를 반복 적 으로 소개 할 가능성 이 높다.
 
Input
여러 그룹 을 포함 하 는 데 이 터 를 입력 하 십시오.
각 조 의 데이터 첫 줄 은 두 개의 정수 n (1 < = n < = 1000), m (1 < = m < = 5000) 을 포함 하고 유채꽃 왕국의 엘 프 수량 과 엘 프 간 의 관계 조 수 를 나타 낸다.
두 번 째 줄 은 n 개의 정 수 를 포함 하고 엘 프 들 의 능력 치 k (1 < = k < = 100000000) 를 나타 낸다.
이어서 m 줄 이 있 습 니 다. 줄 마다 두 개의 다른 정수 u, v (1 < = u, v < = n) 가 있 습 니 다. 엘 프 u 와 엘 프 v 는 같은 가족 에 속 합 니 다.
 
Output
위망 치가 가장 큰 가문 의 위망 치 를 출력 하 십시오. 각 그룹의 데 이 터 는 한 줄 의 출력 에 대응 합 니 다.
 
Sample Input
2 1
1 4
1 2
 
Sample Output
1
피 보 나치 수열 의 성장 속 도 는 매우 빨 라 서 45 번 째 때 이미 100000000 을 넘 었 다. 45 자리 배열 만 열 면 차이 가 많 지 않다. 그 다음 에 이 작은 배열 을 쓸 어 피 보 나치 수 인지 아 닌 지 판단 하면 된다.
u 와 v 를 같은 가족 에 게 합병 하여 사용 하고 집합 을 찾 게 합 니 다. 마지막 으로 뿌리 노드 를 쓸 어 집합 위망 의 최대 치 를 찾 습 니 다.

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <algorithm>

using namespace std;

struct node {
	int w;  //             
	int p;  //    
};

const int maxn = 45;
int a[50];
node f[1005];

void fbb() {   //        
	a[1] = a[2] = 1;
	for (int i = 3; i <= maxn; i++) {
		a[i] = a[i - 1] + a[i - 2];
	}
}

int getf(int v) {   //  v    
	if (f[v].p == v) {
		return v;
	}
	else {
		f[v].p = getf(f[v].p);   //    
		return f[v].p;
	}
}

void Merge(int u, int v) {  //  u, v
	int t1 = getf(u);
	int t2 = getf(v);
	if (t1 != t2) {   //u, v        
		f[t2].p = t1;  // v   u    ，  u      v    
		f[t1].w += f[t2].w;  //        u        ，             
	}
}

int main()
{
	int n, m;
	fbb();
	while (~scanf("%d%d", &n, &m)) {
		for (int i = 1; i <= n; i++) {
			f[i].p = i;  //                
			f[i].w = 0;
			int t;
			scanf("%d", &t);
			for (int j = 1; j <= maxn; j++) {
				if (t == a[j]) {
					f[i].w = 1;   //           
					break;
				}
			}
		}
		for (int i = 1; i <= m; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			Merge(u, v);	//     u,v
		}
		int maxn = numeric_limits<int>::min();
		for (int i = 1; i <= n; i++) {
			if (getf(i) == i) {  //             ，       maxn
				maxn = max(maxn, f[i].w);
			}
		}
		printf("%d
", maxn);
	}
	return 0;
}