알고리즘 공부

백준 효율적인 해킹

컴퓨터과학 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;
}