[백준] 11724

dfs로 풀었는데 분명 연결 요소 개수는 분명 맞는데 자꾸 50%에 틀리던 중, 아무것도 연결 되지 않은 것도 연결 요소로 count해야 한다고 한다. 젠장 한시간 뻘짓함

예시 ) 간선이 5개고 (1,2), (2,3), (3,4)로 주어지면 정답은 2 여야 한다. (5는 아무것도 연결되어 있지 않음)

dfs 코드를 그대로 두고, 입력을 다 받은 뒤 빈 행을 체크해서 연결요소를 +1 해주어서 해결

 

#include <bits/stdc++.h>
//#define INF 1e9
using namespace std;

int n, m;
int **arr;
int cnt;
stack<pair<int, int>> s;
void dfs()
{
	while(!s.empty()){
		int y=s.top().second;
		//cout<<"y : "<< y<<'\n';
		int i=1;
		for(; i<=n; i++){
			if(arr[y][i]==1){
				arr[y][i]=0;
				s.push({y,i});
				break;
			}
		}
		if(i==n+1){
			s.pop();
		}
	}
	cnt++;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    
	cin >> n >> m;

	arr = new int *[n + 1]();
	for (int i = 1; i <= n; i++)
	{
		arr[i] = new int[n + 1]();
	}

	while (m--)
	{
		int x, y;
		cin >> x >> y;
		arr[x][y] = 1;
		arr[y][x] = 1;
	}

	for(int i=1; i<=n; i++){
		int none=0;
		for(int j=1; j<=n; j++){
			if(arr[i][j]==1)none=1;
		}
		if(none==0)cnt++;
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (arr[i][j] == 1)
			{
				s.push({i, j});
				arr[i][j]=0;
				dfs();
			}
		}
	}

	cout << cnt;
	return 0;
}