05 - 트 리 8 파일 전송 (파일 전송) - 경로 압축

제목 설명 우 리 는 컴퓨터 의 네트워크 와 양 방향 연결 의 목록 을 가지 고 있 습 니 다. 각 연결 은 한 컴퓨터 에서 다른 컴퓨터 로 파일 을 전송 할 수 있 습 니 다. 네트워크 의 모든 컴퓨터 에서 다른 컴퓨터 로 파일 을 전송 할 수 있 습 니까?우 리 는 컴퓨터 네트워크 와 양 방향 연결 목록 을 가지 고 있다.모든 연결 은 한 컴퓨터 에서 다른 컴퓨터 로 의 파일 전송 을 허용 한다.네트워크 에 있 는 모든 컴퓨터 에서 다른 컴퓨터 로 파일 을 보 낼 수 있 습 니까?
입력 사양: 입력 규격: 각 입력 파일 은 하나의 테스트 케이스 를 포함 합 니 다. 각 테스트 케이스 의 경우 첫 번 째 줄 에는 네트워크 에 있 는 컴퓨터 의 총 수 N (2 ≤ N ≤ 10 ^ 4) 이 포함 되 어 있 습 니 다. 네트워크 에 있 는 각 컴퓨터 는 1 과 N 사이 의 양의 정수 로 표 시 됩 니 다. 그런 다음 다음 줄 에서,the input is given in the format: 입력 파일 마다 테스트 용례 가 포함 되 어 있 습 니 다.각 테스트 용례 에 대해 첫 번 째 줄 은 N (2 ≤ ≤ 1 0 ^ 4), 한 네트워크 의 컴퓨터 총 수 를 포함한다.그리고 네트워크 의 모든 컴퓨터 는 1 에서 1 사이 의 정수 로 ñ 을 나타 낸다.그리고 다음 줄 에 다음 형식 으로 입력 하 십시오.
I c1 c2 where I stands for inputting a connection between c1 and c2; or 그 중 I 는 입력 c1 과 사이 의 연결 c2 를 표시 합 니 다.아니면
C c1 c2 where C stands for checking if it is possible to transfer files between c1 and c2; or where C 는 c1 과 사이 에 파일 c2 를 전송 할 수 있 는 지 확인 합 니 다.아니면
S where S stands for stopping this case.
출력 사양: 출력 규격: 각 C 케이스 의 경우 각각 c1 과 c2 간 에 파일 을 전송 할 수 있 거나 불가능 한 경우 한 줄 로 "예"또는 "아니오"라 는 단 어 를 인쇄 합 니 다. 각 케이스 의 끝 에 한 줄 로 인쇄 합 니 다. "네트워크 가 연결 되 어 있 습 니 다."or "There are k components."where k is the number of connected components in this network. 각 C 의 경우 c1 과 사이 에 파일 을 전송 할 수 있 거나 불가능 할 경우 한 줄 에 "예"또는 "아니오"c2 를 인쇄 합 니 다.모든 상황 이 끝 날 때 한 줄 에 '네트워크 연결 됨' 을 인쇄 합 니 다.만약 어떤 컴퓨터 사이 에 경로 가 있다 면;또는 "k 구성 요소 가 있 습 니 다."k 이 네트워크 에 연 결 된 구성 요소 의 수 는 어디 에 있 습 니까?
샘플 입력 1: 샘플 입력 1: 5 C 3 2 I 3 2 C 1 5 I 2 4 C 3 5 S
샘플 출력 1: 샘플 출력 1: 아니요 예 2 개의 구성 요소 가 있 습 니 다.
샘플 입력 2: 샘플 입력 2: 5 C 3 2 I 3 2 C 1 5 I 4 I 2 4 C 3 5 I 1 3 C 1 5 S
샘플 출력 2: 샘플 출력 2: 아니오 예 네트워크 가 연결 되 어 있 습 니 다.
사고방식 해답: 기초 조작
코드 설명:

#include
#include
#define Maxsize 10000
int Arry[Maxsize]; 
int FindRoot(int num);
void Connect();
void Check();
void Compute(int N);
int main()
{
	int N,i = 0;
	char ch;
	scanf("%d",&N);//      
	for(i = 1; i <= N ;i++)//    
		Arry[i] = -1;
	scanf("%c",&ch);//    
	while( ch != 'S')
	{
		switch( ch )
		{
			case 'C':Check();break;//  
			case 'I':Connect();break;//  
			default:break;
		}
		scanf("%c",&ch);
	} 
	if(ch == 'S')
		Compute(N);//       
	return 0;
}
int FindRoot(int num)//  ，    ：    ；      X     ；     。
{
	if( Arry[num] < 0)//    ，  
		return num;
	else
		return Arry[num] = FindRoot(Arry[num]);//   
}
void Connect()
{
	int num1,num2,root1,root2;
	scanf("%d %d",&num1,&num2);
	root1 = FindRoot(num1);//  
	root2 = FindRoot(num2);
	if(root1 != root2)//     
	{
		if(Arry[root1] < Arry[root2])//             
		{
			Arry[root1] += Arry[root2]; 
			Arry[root2] =  root1; 
		}
		else
		{
			Arry[root2] += Arry[root1]; 
			Arry[root1] =  root2; 
		}
	}
	return ;
}
void Check()
{
	int num1,num2,root1,root2;
	scanf("%d %d",&num1,&num2);
	root1 = FindRoot(num1);
	root2 = FindRoot(num2);
	if(root1 != root2)
		printf("no
");
	else
		printf("yes
");
	return ; 
}
void Compute(int N)
{
	int counter = 0,i = 0;
	for(i = 1; i <= N ;i++)
		if(Arry[i] < 0) counter++;
	if(counter == 1)
		printf("The network is connected.
");
	else
		printf("There are %d components.",counter);
	return ; 
}