PTA File Transfer

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?
Input Specification:
Each input file contains one test case. For each test case, the first line contains N (2≤N≤10​4​​), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:

where  I  stands for inputting a connection between  c1  and  c2 ; or

where  C  stands for checking if it is possible to transfer files between  c1  and  c2 ; or

where  S  stands for stopping this case. 
Output Specification:
For each  C  case, print in one line the word "yes" or "no" if it is possible or impossible to transfer files between  c1  and  c2 , respectively. At the end of each case, print in one line "The network is connected." if there is a path between any pair of computers; or "There are  k components." where  k  is the number of connected components in this network.
 
문제 풀이 방향: 이 문 제 는 주로 집합 간 의 합병 과 검색 을 설계 하고 데이터 구 조 를 찾 아 결점 간 의 관 계 를 저장 해 야 한다.(PTA 에서 이 문 제 는 쌓 여 있 는 한 장 안에 놓 여 있 습 니 다. 낡은 사고 에 얽 매 일 수 있 습 니 다. 저 는 이 문제 와 쌓 여 있 는 구조의 관 계 를 생각 하지 못 했 습 니 다. (유일한 관 계 는 똑 같이 배열 로 저장 하 는 것 입 니까?) 그리고 아 끼 지 않 고 가르쳐 주 십시오.
  비교적 교묘 한 것 은 같은 뿌리 여 부 를 이용 하여 두 결점 이 같은 집합 인지 아 닌 지 를 판단 하 는 것 이다. 같은 뿌리 를 찾 는 방식 은 압축 경로 이 고 이 나무의 깊이 를 유지 하 는 방식 은 순서대로 병합 하 는 것 이다.
  번호 의 부모 노드 를 배열 로 저장 합 니 다.
  find 함수 부모 노드 되 돌리 기  

int find(int num)//    
{
    return fa[num]==0?num:find(fa[num]);
}

 순위 에 따라 병합 하 는 방식 으로 나무의 깊이 를 압축 한다. 즉, 순위 (rank) 가 큰 나 무 를 주근 노드 로 하면 나무의 깊이 가 계속 증가 하 는 것 을 효과적으로 피 할 수 있다.
  지적 해 야 할 것 은 인터넷 의 글 을 본 후에 모두 가 질 서 를 따라 합병 하 는 것 이 일반 병합 의 장점 에 비해 현저 한 지적 을 하지 않 았 다 는 것 이다. 여기 서 먼저 제 생각 은 경로 압축 으로 뿌리 노드 를 찾 은 후에 뿌리 노드 의 크기 에 따라 연결 하 는 것 입 니 다. 그러면 이미 정 해진 정렬 방식 을 초래 한 후에 (예 를 들 어 뿌리 대련 은 뿌리 가 작은 아래 에 있 습 니 다)데 이 터 를 반대 순서 로 입력 하면 나무의 깊이 가 선형 으로 증가 할 수 있 으 며, 순위 에 따라 병합 하면 이 상황 을 피 할 수 있 습 니 다. 영원히 순위 가 높 은 뿌리 아래 에 연결 되 어 있 기 때 문 입 니 다.

//    
if(rank[root1]rank[root2])
    {
        fa[root2]=root1;
        rank[root1]++;
        num--;
    }
    else
    {
        fa[root1]=root2;
        rank[root2]++;
        num--;
    }

 
최종 코드:

#include 
void check(void);
void initial(void);
int find(int);
int fa[10005],rank[10005],num;
int main(void)
{
    char ch;
    scanf("%d",&num);
    while((ch=getchar())!='S')
    {
        switch (ch) {
            case 'C':
                check();
                break;
            case 'I':
                initial();
            default:
                break;
        }
    }
    if(num==1)
        printf("The network is connected.
");
    else
        printf("There are %d components.
",num);
}

void check(void)
{
    int num1,num2;
    scanf("%d %d",&num1,&num2);
    int root1=find(num1);
    int root2=find(num2);
    if(root1==root2)
        printf("yes
");
    else
        printf("no
");
}

void initial(void)
{
    int num1,num2;
    scanf("%d %d",&num1,&num2);
    int root1=find(num1);
    int root2=find(num2);
    if(root1==root2)
        return;
    if(rank[root1]rank[root2])
    {
        fa[root2]=root1;
        rank[root1]++;
        num--;
    }
    else
    {
        fa[root1]=root2;
        rank[root2]++;
        num--;
    }
}

int find(int num)
{
    return fa[num]==0?num:find(fa[num]);
}

마지막 으로 테스트 데 이 터 를 첨부 합 니 다.
https://img-blog.csdn.net/20161003210307030?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center (CSDN 블 로 거 타임 킬러 타임 의 글 에서 발췌)