모음 집 - 바이트 점프

반 에는 N 명의 학생 이 있다.그 중 어떤 사람 은 친구 이 고, 어떤 사람 은 그렇지 않다.그들의 우정 은 전달 성 을 가지 고 있다.A 는 B 의 친구 이 고 B 는 C 의 친구 라 는 것 을 알 고 있다 면 우 리 는 A 도 C 의 친구 라 고 생각 할 수 있다.이른바 친구 권 이란 모든 친구 의 집합 을 가리킨다.N * N 의 행렬 M 을 지정 하여 학급 중 학생 간 의 친구 관 계 를 나타 낸다.만약 에 M [i] [j] = 1 은 i 번 째 와 j 번 째 학생 이 서로 친구 가 되 는 것 을 알 고 있 음 을 나타 낸다. 그렇지 않 으 면 모른다.너 는 모든 학생 들 이 이미 알 고 있 는 친구 권 의 총 수 를 출력 해 야 한다.예 1: 입력: [1, 1, 0], [1, 1, 0], [0, 0, 1] 출력: 2 설명: 이미 알 고 있 는 학생 0 과 학생 1 은 서로 친구 이 고 그들 은 한 친구 권 에 있다.두 번 째 학생 은 스스로 친구 권 에 있다.그래서
그리고 전형 적 인 문 제 를 찾 아 보 자. 즉, 전체 그림 에 모두 몇 개의 연결 분기 2 차원 행렬 M 은 점 과 점 간 의 관 계 를 나타 낸다. 만약 에 M [i] [j] = 1 이 있 으 면 우 리 는 i 와 j 를 연결 할 수 있다. merge (int i, int j) 우 리 는 하나의 배열 pre [] 로 모든 점 의 전도 점 을 저장 할 수 있다. pre [i] = j 는 i 의 전도 점 이 j 임 을 나타 낸다.같은 연결 지점 에 속 하 는 점 을 서로 연결 시 키 기 위해 모든 연결 지점 에 하나의 메 인 노드 가 있다 고 가정 하고 선도 노드 는 그 자체 의 그 점 이 바로 메 인 노드 이다.이 연결 지점 에 속 하 는 모든 점 은 선도 점 을 통 해 이 메 인 노드 를 찾 을 수 있 습 니 다.우 리 는 함수 find 를 통 해 현재 노드 가 속 한 분기 의 주 노드 를 찾 을 수 있 습 니 다.

vector<int> pre;//         
int find(int root) //     
{
	int son, tmp;
	son = root;
	while(root != pre[root]) //     
		root = pre[root];
	while(son != root) //    
	{
		tmp = pre[son];
		pre[son] = root;
		son = tmp;
	}
	return root;//     
}
void merge(int x,int y)
{
    pre[find(y)]=find(x);// x      y    
}
int findCircleNum(vector<vector<int>>& M) 
{
    int n=M.size();
    pre.assign(n,0);
    for(int i=0;i<n;++i)
        pre[i]=i;//             
    for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j)
            if(M[i][j])
                merge(i,j);//  i,j
    int ans=0;
    for(int i=0;i<n;++i)
        if(i==pre[i])//                
            ++ans;
    return ans;
}

그 중의 경로 압축 은 각 노드 의 전 도 를 찾 은 메 인 노드 로 설정 하 는 것 이다.이렇게 되면 경 로 를 찾 을 때마다 2 층 밖 에 없어 요.