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 |