알고리즘 공부
백준 효율적인 해킹
컴퓨터과학
2023. 8. 2. 23:08
https://www.acmicpc.net/problem/1325
1325번: 효율적인 해킹
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한
www.acmicpc.net
dfs와 인접 리스트 문제
#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<map>
#include<stack>
using namespace std;
struct Point {
int s, e, t, cnt, power;
char c;
};
void Prints(vector<vector<int>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<bool>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<char>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<vector<char>>>maps, int n, int m, int k) {
for (int t = 0; t < k; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[t][i][j];
}
cout << endl;
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<vector<bool>>>maps, int n, int m, int k) {
for (int t = 0; t < k; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[t][i][j];
}
cout << endl;
}
cout << endl;
}
cout << endl;
}
void Prints(vector<int>line, int n) {
for (int i = 0; i < n; i++) {
cout << line[i] << ",";
}
cout << endl;
}
void Prints(string str, int n) {
for (int i = 0; i < n; i++) {
cout << str[i] << ",";
}
cout << endl;
}
struct Data {
int index;
int score;
};
vector<int>computer;
vector<bool>bVisited;
vector<Point>lists;
vector<vector<int>>glistmap;
int n, m,gcnt;
void dfs(int k) {
//k=1
bVisited[k - 1] = true;
for (int i = 0; i < glistmap[k].size(); i++) {
//3
if (bVisited[ glistmap[k][i]-1 ]==false) {
//cout << k << ",";
//cout << glistmap[k][i]<< ",";
gcnt++;
dfs(glistmap[k][i]);
}
}
}
bool cmp(const Data& a, const Data& b) {
if (a.score== b.score) {
return a.index < b.index;
}
return a.score > b.score;
}
int main() {
cin >> n>>m;
vector<bool>initbVisited;
vector<Data>ranks;
vector<vector<int>>listmap(n+1);
for (int i = 0; i < n; i++) {
computer.push_back(i + 1);
bVisited.push_back(false);
}
initbVisited = bVisited;
for (int i = 0; i < m; i++) {
Point tmpp;
int s;
int e;
cin >> s>>e;
tmpp.s = s;
tmpp.e = e;
lists.push_back(tmpp);
listmap[e].push_back(s);
}
glistmap = listmap;
//cout << glistmap[1][0];
//e->s
for (int i = 0; i < n; i++) {
//cout << computer[i] << ",";
gcnt = 1;
Data tmpD;
dfs(computer[i]);
//cout << endl;
tmpD.index = computer[i];
tmpD.score = gcnt;
ranks.push_back(tmpD);
bVisited =initbVisited;
}
if (ranks.size() > 0) {
sort(ranks.begin(), ranks.end(), cmp);
Data tmpD = ranks[0];
for (int i = 0; i < ranks.size(); i++) {
if (tmpD.score == ranks[i].score) {
cout << ranks[i].index << " ";
}
}
}
return 0;
}