친구 권C++_Med
1726 단어 데이터 구조
하 나 를 정 하 다 N * N 행렬 M. 반 중 학생 간 의 친구 관 계 를 나타 낸다.만약 에 M [i] [j] = 1 은 i 번 째 와 j 번 째 학생 이 서로 친구 가 되 는 것 을 알 고 있 음 을 나타 낸다. 그렇지 않 으 면 모른다.너 는 모든 학생 들 이 이미 알 고 있 는 친구 권 의 총 수 를 출력 해 야 한다.
예시 1:
입력: [[1,1,0], [1,1,0], [0, 0, 1] 출력: 2 설명: 이미 알 고 있 는 학생 0 과 학생 1 은 서로 친구 이 고 그들 은 한 친구 권 에 있다.두 번 째 학생 은 스스로 친구 권 에 있다.그래서예시 2:
입력: [[1,1,0], [1,1,1], [0, 1, 1] 수출: 1 설명: 이미 알 고 있 는 학생 0 과 학생 1 은 서로 친구 이 고 학생 1 과 학생 2 는 서로 친구 이기 때문에 학생 0 과 학생 2 도 친구 이기 때문에 그들 세 사람 은 한 친구 권 에서 1 로 돌아간다.주의:
N 은 [1, 200] 범위 내 에 있다.모든 학생 에 게 는 M [i] [i] = 1 이 있 습 니 다.M [i] [j] = 1 이 있 으 면 M [j] [i] = 1 이 있다.
사고: 이 이 치 는 주로 깊이 우선 검색 과 비슷 하 다. 친구 권 은 전달 성 이 있 고 우리 가 B 가 A 의 친구 권 이라는 것 을 검색 할 때 B 의 친구 권 에 어떤 친구 가 있 는 지 검색 해 야 한다.visited 배열 을 이용 하여 학우 들 의 표 시 를 잘 하 다.
C + + 코드 는 다음 과 같 습 니 다.
class Solution {
// i
void find(vector>& M,int i, vector& visited)
{
visited[i] = true;
for(int j=0; j< M.size(); j++)
{
if(M[i][j] ==0 || visited[j] == true) continue; //
find(M,j,visited);
}
}
public:
int findCircleNum(vector>& M) {
int n = M.size();
if(n == 0) return 0;
int res=0;
vector visited(n, false); //
for(int i=0; i < n; i++)
{
if(visited[i] == true) continue;
find(M,i,visited);
res++;
}
return res;
}
}; 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
