PAT 갑 급 1004 문제 풀이 - 그리고 사상 개선 을 조사 합 니 다.

제목 분석: 본 문 제 는 모든 노드 를 적당 한 데이터 구 조 를 통 해 저장 하 는 방법 (한 쌍 이 많은 관계) 을 고려 해 왔 다. 마지막 으로 집합 을 통 해 하나의 배열 p, p [i] i 노드 를 저장 하 는 부모 노드 를 발견 했다. 매번 조회 번호 가 i 인 노드 는 몇 번 째 층 에 속 하고 이 점 의 부모 요소 로 하 는 노드 가 있 는 지 판단 했다.(이 점 이 잎 노드 인지 판단 하면 floor [대응 층수] +) 본 문제 의 그림 에 순환 도로 가 존재 하지 않 기 때문에 이 p 배열 을 통 해 나무 전 체 를 교묘 하 게 저장 할 수 있 습 니 다. 본 문 제 는 vis [] 배열 을 통 해 특정한 노드 가 나 타 났 는 지 (N 개의 노드 가 반드시 질서 있 게 나타 나 지 않 기 때 문) 를 저장 할 수 있 습 니 다. mat 배열 은 아래 에 i 로 표 시 될 때 잎 노드 인지, floor [] 를 저장 합 니 다.배열 i 층 의 잎 노드 의 총 수 는 본 문제 에서 주의해 야 할 세부 사항 은 입력 한 N 과 M 이 고 M 은 0 일 수 있 으 며 뿌리 노드 가 반드시 1 이기 때문에 0 층 에 잎 노드 (1 번 노드 자체) 가 있어 야 한다. 그 밖 에 입력 한 모든 줄 의 데이터 에 대해 각 노드 의 아이 노드 수 는 0 (0 은 잎 노드 를 대표 하고 아이 노드 가 없다) 일 수도 있다.

 1 #include
 2 #include<string.h>
 3 using namespace std;
 4 
 5 int vis[105];        //  i          
 6 int floor[105];        //              1 0  
 7 int p[105];            //  i     
 8 int mat[105];         //      i        i
 9 int max_flo;
10 
11 void serach(int x){
12     int t = x;
13     int flo = 0;    //      1    0  
14     while(p[x] != x){
15         x = p[x];
16         flo++;    
17     }
18     if(flo > max_flo) max_flo = flo; 
19     if(mat[t] == 0){//                                      +1 
20         floor[flo]++;    
21     }     
22 }
23 
24 int main(){
25     int n, m;
26     while(scanf("%d", &n) != EOF){
27         if(n == 0) break;
28         scanf("%d", &m);
29         memset(floor, 0, sizeof(floor));
30         memset(vis, 0, sizeof(vis));
31         memset(mat, 0, sizeof(mat));
32         if(m == 0) floor[0]++;
33         max_flo = 0;                //         
34         for(int i = 1; i <= 100; i++) p[i] = i;
35         for(int i = 1; i <= m; i++){
36             int id, num;
37             scanf("%d%d", &id, &num);
38             vis[id] = 1;
39             if(num != 0) mat[id] = 1;
40             for(int j = 1; j <= num; j++){
41                 int x;
42                 scanf("%d", &x);
43                 p[x] = id;
44                 vis[x] = 1;
45             }
46         }
47         for(int i = 1; i <= 100; i++){
48             if(vis[i] == 1){        //              
49                 serach(i);
50             }
51         }
52         for(int i = 0; i <= max_flo; i++){
53             if(i != 0) printf(" ");
54             printf("%d", floor[i]);
55         }
56         printf("
");
57     }
58     return 0;
59 }