11724 DFS 연결 요소의 개수

11724 오답

인접행렬 사용

m 간선의 최대 개수가 N(N-1) / 2 인데 이는 nC2로
인접 행렬에서 자기 자신으로 가는 간선을 제외한 나머지의 간선 개수를 말하는데
n개의 정점에서 2개의 점을 선택하여 n개의 정점에서 가능한 간선의 개수를 의미한다.
간선의 개수가 많은 경우 인접행렬을 사용하면 좋다.

DFS에서 사용할 전역변수

static method 인 main, dfs에서 사용할 전역변수
class 안 main 밖에 static 변수를 선언 main에서 초기화,
인접행렬 초기화 위해 크기를 입력받은후 선언 ,

static int graphs[][];
static boolean visited[];
static int N, cnt;

연결요소 개수 구하는 법

한 노드에서 시작한 DFS의 재귀호출이 끝났을 때 cnt++, 연결요수의 개수

그래프에서 연결 노드 주어졌을 때

for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			// 무방향 그래프 특성.
			arr[x][y] = 1;
			arr[y][x] = 1;
		}

인접행렬 그래프 DFS 구현

static void DFS(int value) {
		
		if(node[value] == true) {
			return;
		}

		node[value] = true;
		for(int i=1; i<=N; i++) {
			if(arr[value][i] == 1) {
				DFS(i);
			}
		}
	}