백준 11724번 연결 요소의 개수

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>> line;
bool visited[1000];

bool dfs(int x)
{
	visited[x] = true;
	
	for (int i = 0; i < line.size(); ++i) {
		if (line[i].first == x && !visited[line[i].second])
			dfs(line[i].second);
		else if (line[i].second == x && !visited[line[i].first])
			dfs(line[i].first);
	}

	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;	// n: 정점, m: 간선
	cin >> n >> m;

	line.resize(m + 1);
	for (int i = 0; i < m; ++i)
		cin >> line[i].first >> line[i].second;

	int result = 0;
	for (int i = 0; i < m; ++i)
		if (!visited[line[i].first]
			&& dfs(line[i].first))
			++result;
	
	for (int i = 1; i <= n; ++i)
		if (!visited[i])
			++result;

	cout << result << endl;

	return 0;
}

시간이 다른 사람보다 많이 나와서 고민 좀 더 해봐야 하는 문제..

 

----------------------------------------------------------------

다시 풀은 코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;	// n: 정점, m: 간선
vector<int> graph[1001];
bool visited[1001];

bool dfs(int x)
{
	visited[x] = true;

	for (int i = 0; i < graph[x].size(); ++i)
		if (!visited[graph[x][i]])
			dfs(graph[x][i]);

	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	int u, v;
	for (int i = 0; i < m; ++i) {
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	int result = 0;
	for (int i = 1; i <= n; ++i)
		if (!visited[i] && dfs(i))
			++result;
	
	cout << result << endl;

	return 0;
}

 

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수