NOI 4.3 도 론 1526: 종교 신앙

제목:http://noi.openjudge.cn/ch0403/1526/
1526: 종교 신앙
총 시간 제한: 5000ms 메모리 제한: 65536kB
묘사 하 다.
세상 에는 많은 종교 가 있 습 니 다. 당신 이 흥 미 를 느끼 는 것 은 당신 학교의 학우 들 이 몇 가지 종 교 를 믿 는 지 입 니 다.
당신 의 학교 에는 n 명의 학생 (0 < n < = 50000) 이 있 습 니 다. 당신 은 모든 사람의 종교 신앙 에 대해 물 어 볼 수 없습니다. 왜냐하면 그들 은 밝 히 기 를 원 하지 않 기 때 문 입 니 다.그러나 두 명의 학생 을 동시에 찾 았 을 때 그들 은 같은 종 교 를 믿 는 지 여 부 를 알려 주 고 싶 어 한다. 이런 질문 을 통 해 학교의 종교 수의 상한 선 을 추산 할 수 있다.너 는 모든 학생 들 이 가장 많은 종교 만 믿는다 고 생각 할 수 있다.

입력
여러 그룹의 데 이 터 를 입력 하 십시오.각 그룹의 데이터 의 첫 줄 은 n 과 m, 0 < = m < = n (n - 1) / 2 를 포함 하고 그 다음 에 m 줄 은 두 개의 숫자 i 와 j 를 포함 하 며 학생 i 와 학생 j 가 같은 종 교 를 믿 고 학생 들 은 1 에서 n 으로 표시 된다.입력 은 한 줄 n = m = 0 으로 끝 납 니 다.
출력
각 그룹의 데이터 에 대해 먼저 번호 (1 부터) 를 출력 한 다음 에 학생 들 이 믿 는 서로 다른 종교 의 수량 상한 선 을 출력 한다.
샘플 입력

샘플 출력

Case 1: 1
Case 2: 7

-----------------------------------------------------
사고의 방향
제목: 그림 속 노드 의 연결 관 계 를 알 고 그림 속 의 연결 수량 을 구 합 니 다.
템 플 릿 문 제 를 수집 합 니 다.그리고 조사 집 에 대한 상세 한 소 개 는 이 신기 한 박문 을 볼 수 있 고 매우 재 미 있 는 것 과 상세 한 설명 을 찾 을 수 있다.
-----------------------------------------------------
코드

//    

#include
#include
using namespace std;

const int NMAX = 50005;
int pre[NMAX] = {};								//         
int n = -1;										//     ：    
int cnt = n;									//     ：      

int find(int x)									//          ，              
{
	int r = pre[x],t = x;
	while (r!=t)								//        （   ==  ），     
	{
		t = r;
		r = pre[t];
	}
	//       
	t = x;
	int tt = x;
	while (t!=r)								//          ，                    
	{
		tt = pre[t];
		pre[t] = r;
		t = tt;
	}

	return r;
}

void join(int x, int y)							//           
{
	int xx = find(x), yy = find(y);				//             
	if ( xx!= yy)								//             ,      ;                
	{
		cnt--;									//       -1
		pre[xx] = yy;							//                         
	}
}



int main()
{
#ifndef ONLINE_JUDGE
	ifstream fin ("0403_1526.txt");
	int m,i,x,y,t=0;
	while (fin >> n >> m)
	{
		if (n==0 && m==0)
		{
			break;
		}
		for (i=0; i> x >> y;
			join(x,y);
		}
		cout << "Case "<< (++t) << ": " << cnt << endl;
	}
	fin.close();
#endif
#ifdef ONLINE_JUDGE
	int m,i,x,y,t=0;
	while (cin >> n >> m)
	{
		if (n==0 && m==0)
		{
			break;
		}
		for (i=0; i> x >> y;
			join(x,y);
		}
		cout << "Case "<< (++t) << ": " << cnt << endl;
	}
#endif
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

조세 프 링 문제 (구조 체 지침 실현)

#include<stdio.h> #include<stdlib.h> struct node{ int data; struct node *next; }; int main(){ int i,j,k,m,n; struct node...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

NOI 4.3 도 론 1526: 종교 신앙

좋은 웹페이지 즐겨찾기