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

 

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어

www.acmicpc.net

메모리,시간 초과 뜨면 ㅠㅠ 휴 최적화가 더힘드렁

#include <iostream>
#include <vector>
#include <algorithm>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<bitset>
using namespace std;

void Prints(vector<vector<char>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<bool>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<int>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
struct Point {
	int u;
	int v;

};
int main() {
	int n, m;
	cin >> n >> m;
	vector<Point>maps;
	vector<bool>bVisited(m, false);
	vector<bool>bCountVisited(n, false);//0,1,2,3,4,5
	for (int i = 0; i < m; i++) {
		Point p;
		cin >> p.u;
		cin >> p.v;
		maps.push_back(p);
	}
	int count = 0;
	queue<int>q;
	for (int z = 0; z < n; z++) {

		int init = z+1;
		if (bCountVisited[z] == false) {
			count++;
			q.push(init);
			bCountVisited[z] = true;
			while (!q.empty()) {
				int start = q.front();
				
				q.pop();
				for (int i = 0; i < m; i++) {

					if (start == maps[i].u&& bCountVisited[maps[i].v-1] == false) {
						bCountVisited[maps[i].v - 1] = true;
						q.push(maps[i].v);

					}
					if (start == maps[i].v&& bCountVisited[maps[i].u - 1] == false) {
	
						bCountVisited[maps[i].u - 1] = true;
						q.push(maps[i].u);

					}
					
				}
			}
			//cout << endl;
		}
	}
	cout << count;
	return 0;
}

'알고리즘 공부' 카테고리의 다른 글

백준 Puyo Puyo  (0) 2023.07.13
백준 케빈 베이컨의 6단계 법칙  (0) 2023.07.12
백준 다리 만들기  (0) 2023.07.12
백준 dfs와 bfs  (0) 2023.07.11
백준 안전 영역  (0) 2023.07.09

+ Recent posts