Algorithm/위상정렬

백준 21276 계보복원가호석 c++ // 위상정렬, 조상찾기주의점, 문자열을 idx로 바꿔서 풀어라

https://www.acmicpc.net/problem/21276 1. 문자열을 idx로 바꿔서 풀어라1. map m을 두고 sort 후m["철수"] = 0 , m["석열"]=1 ... 이런식으로 할당하면 된다.2. 이래야 실수를 줄이고 디버깅, 복잡도등 이점이 많다.. 2. 조상찾기주의점석호 철수(조상) 일때,석호 그래야 철수의 indegree가 0이됨.* 위상정렬의 기본 idea가 indegree가 0인점을 제거해 나간다는 점을 꼭 생각할것!! 3. 의사코드1. 문자열을 idx로 바꿈2. 입력만 문자열일뿐 숫자 위상정렬과 같이 생각하면 쉽다.자료구조가 숫자 그자체에서 해당 idx로 바뀌었을 뿐이다.vector adj[1001]; //i노드의 인접리스트들의 idxvector child[1001]; /..

백준 2623 음악프로그램 c++ // 위상정렬, 사이클 검사방법

https://www.acmicpc.net/problem/2623 1. 사이클 검사방법결론 : 큐를 탐색하면서 , 차수가 0인애를 result에 담고, result.size가 n이아니면 사이클이 있는것임!이유 : 위와 같을때, a가 큐에들어가려면 c가 없어지면서 deg[a]-1 해줘야 되고c가 큐에 들어가려면 b가없어지면서 deg[c]-1 해줘야 되는데a,b,c는 서로가 없어져야 큐에들어갈수 있음 -> 그런데 데드락처럼 큐에 들어갈수없는 존재들이다.따라서 사이클이 있는 a,b,c는 정답에 들어가지 않음 -> result.size()가 4(n)가 아닌 1이 되어있음 2. 전체코드#include using namespace std;typedef long long ll;vector adj[10001]; //i..

백준 2252 줄세우기 c++ // 위상정렬

https://www.acmicpc.net/problem/2252 1. 위상정렬주로 수강신청시 선수과목, 줄세우기 등순서를 정해야하는 문제일때, 사용하면 된다. 2. 의사코드1. degree : 나한테 들어오는 화살표의 갯수 // a->b2. degree가 0이다 -> 맨앞에 와도 ok -> 큐에넣기3. 맨앞에 오고, 연결노드들의 차수 -1 해주기.4. 연결노드들의 차수가 0이다? -> 큐에넣기5. 큐가빌때까지 반복 3. 전체코드#include using namespace std;typedef long long ll;vector adj[32001]; //i노드의 인접노드들int deg[32001]; // i노드의 차수int n, m;int main() { ios_base::sync_with_stdi..