병 찰 집

병 찰 집
작년 겨울방학 에 막 공 부 를 마치 고 집 을 찾 았 을 때 이 문 제 를 만 났 을 때,나 는 사용 하고 집 을 찾 았 다 는 것 을 알 았 지만,왜 이렇게 해 야 하 는 지 이해 가 되 지 않 았 다.올 해 는 pta 를 닦 고 또 이 문 제 를 만 나 감개 무량 했다.
사용 하고 집합 을 찾 으 려 면 반드시 father 배열 을 초기 화해 야 합 니 다.사용 하고 집합 을 찾 으 려 면 father 배열 을 초기 화해 야 합 니 다.사용 하고 집합 을 찾 으 려 면 father 배열 을 초기 화해 야 합 니 다.중요 한 일 은 세 번 말 해 야 합 니 다.왜냐하면 저 는 매번 잊 어 버 리 기 때 문 입 니 다.

const int maxn=1e5;
//father         ，            ，
//  ，             findfather   
int father[maxn]; 
int findfather(int x)
{
	if(x==father[x]) return x;
	else
	{
		father[x]=findfather(father[x]);
		return father[x];
	}
}
void Union(int x,int y)
{
	int a=findfather(x);
	int b=findfather(y); 
	if(a!=b)
	{
		father[b]=a;
	}
}

L2-024 부락(25 점)
한 지역 사회 에서 모든 사람 은 자신의 작은 범 위 를 가지 고 서로 다른 친구 권 에 속 할 수도 있다.우 리 는 친구 의 친구 들 이 모두 한 부락 에 있다 고 생각 하기 때문에 당신 이 정 해진 지역 사회 에서 도대체 몇 개의 서로 사 귀지 않 는 부락 이 있 는 지 통계 해 보 세 요.그리고 임의의 두 사람 이 같은 부락 에 속 하 는 지 확인한다.입력 형식:
첫 번 째 줄 에 입력 하여 정수 N(≤104)을 드 립 니 다.이미 알 고 있 는 작은 범위 의 개수 입 니 다.그 다음 에 N 줄 은 다음 과 같은 형식 으로 작은 범위 의 사람 을 보 여 줍 니 다.
K P[1] P[2] ⋯ P[K]
그 중에서 K 는 작은 범위 의 인원수 이 고 P[i](i=1,K)는 작은 범위 의 모든 사람의 번호 입 니 다.여기 있 는 모든 사람의 번 호 는 1 부터 연속 으로 번 호 를 매 기 며 최대 번 호 는 104 를 넘 지 않 는 다.
이후 한 줄 에 마이너스 정수 가 아 닌 Q(≤104)를 제시 하 는 것 은 조회 횟수 입 니 다.그 다음 에 Q 줄 은 각 줄 에 조 회 된 사람의 번 호 를 알려 줍 니 다.출력 형식:
먼저 한 줄 에서 이 지역 사회의 총 인원 과 서로 교차 하지 않 는 부락의 개 수 를 수출 한다.그 다음 에 모든 조회 에 대해 그들 이 같은 부락 에 속 하면 한 줄 에 Y 를 출력 하고 그렇지 않 으 면 N 을 출력 합 니 다.입력 샘플:4,3,10,1,2,3,4,4,1,5,7,8,9,6,4,2,10,5,3,7 출력 샘플:102 Y N

#include
using namespace std;
const int maxn=1e5;
//father         ，            ，
//  ，             findfather   
int father[maxn]; 
int findfather(int x)
{
	if(x==father[x]) return x;
	else
	{
		father[x]=findfather(father[x]);
		return father[x];
	}
}
void Union(int x,int y)
{
	int a=findfather(x);
	int b=findfather(y); 
	if(a!=b)
	{
		father[b]=a;
	}
}
set<int>s,s1;
int main()
{
	for(int i=1;i<maxn;i++)
	father[i]=i;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		
		int m,c;
		cin>>m>>c;
		s.insert(c);
		for(int j=2;j<=m;j++)
		{			
			int b;
			cin>>b;
			s.insert(b);
			Union(c,b);
		}
	} 
	set<int>::iterator it=s.begin();
	for(;it!=s.end();it++)
	{
		s1.insert(findfather(*it));
	}
	cout<<s.size()<<" "<<s1.size()<<endl;
	int k;
	cin>>k;
	for(int i=0;i<k;i++)
	{
		int x,y;
		cin>>x>>y;
		int a=findfather(x);
		int b=findfather(y);
		if(a==b) cout<<"Y"<<endl;
		else
		cout<<"N"<<endl;
	}
	
	
}