[HDU 3172 Virtual Friends] 검색 집합 + map 포인터 최적화

제목 링크: http://acm.hdu.edu.cn/showproblem.php?pid=3172
제목: 친 구 를 찾 아 새로운 친 구 를 만나면 친구 들 을 합 쳐 총 친구 수 를 출력 한다.그렇지 않 으 면 이미 같은 곳 에 있다 면 직접 출력 하면 된다.
 
문제 풀이 방향:
 뚜렷 하고 집합 을 찾 으 려 면 친구 수 치 는 하나의 배열 을 열 어 부모 노드 이하 의 범 위 를 저장 해 야 합 니 다. 같은 범위 에서 합병 하지 않 으 면 됩 니 다.
하지만 코드 를 두 드 리 면 TLE 를 과감하게 발견 할 수 있 습 니 다.인터넷 의 많은 문제 풀이 보고서 도 TLE 로 경기 후 데이터 무시 가 많이 강화 되 었 다.
집합 + 맵 폭격 으로 시간 초과 가 분명 합 니 다.여기에 약간의 기교가 있어 맵 에 대해 지침 최적화 처 리 를 한다.
 

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <map>

 4 #include <cstring>

 5 #include <algorithm>

 6 using namespace std;  7 

 8 const int maxn=200005;  9 int pre[maxn],num[maxn]; 10 char str[maxn][25]; 11 

12 int find(int x) 13 { 14     int r=x; 15     while(pre[r]!=r) 16  { 17         r=pre[r]; 18  } 19     return r; 20 } 21 

22 struct cmp 23 { 24     bool operator()(const char* s1,const char* s2)const

25  { 26         return strcmp(s1,s2)<0; 27  } 28 }; 29 

30 int main() 31 { 32     int T, n, fa, fb; 33     while(cin >> T) 34  { 35         while(T--) 36  { 37 

38             scanf("%d",&n); 39             int  cnt=0; 40             map<char*,int,cmp>M; 41             for(int i=0; i<=2*n; i++) 42  { 43                 pre[i]=i; 44                 num[i]=1; 45  } 46             int res=0; 47             for(int i=0; i<n; i++) 48  { 49                 scanf("%s%s",str[++res],str[++res]); 50                 if(!M[str[res-1]]) 51                     M[str[res-1]]=++cnt; 52                 if(!M[str[res]]) 53                     M[str[res]]=++cnt; 54                 fa=find(M[str[res-1]]); 55                 fb=find(M[str[res]]); 56                 int ans=0; 57                 if(fa!=fb) 58  { 59                     num[fa]+=num[fb]; 60                     printf("%d
",num[fa]); 61                     pre[fb]=fa; 62  } 63                 else printf("%d
",num[fa]); 64  } 65  } 66  } 67     return 0; 68 }