[코드트리] 친구의 키 C++

문제

https://www.codetree.ai/missions/9/problems/height-of-friends?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

const int MAX_N = 100'000;

int n, m;
vector<int> edges[MAX_N+1];
bool visited[MAX_N+1]={false, };
stack<int> reversed_order;

void dfs(int x){
    for(auto e: edges[x]){
        if(visited[e]) continue;
        visited[e]=true;
        dfs(e);
    }

    reversed_order.push(x);
}
// 키가 큰 사람부터 내림차순으로
// (a, b) 형태로 주어지며, 이는 a번 친구가 b번 친구보다 키가 크다는 것을 의미
// 친구들이 서있는 순서를 앞에서부터 차례대로 구해주는 프로그램
int main() {
    cin >> n >> m;
    for(int i=0; i<m; ++i){
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
    }

    for(int i=1; i<=n; ++i){
        if(visited[i]) continue;
        visited[i]=true;
        dfs(i);
    }

    while(!reversed_order.empty()){
        cout << reversed_order.top() << " ";
        reversed_order.pop();
    }
    return 0;
}

 

 

indegree 배열을 이용해 queue에 들어온 순서대로 출력

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_N = 100'000;

int n, m;
vector<int> edges[MAX_N+1];
int indegree[MAX_N+1];
queue<int> q;

int main() {
    cin >> n >> m;
    for(int i=0; i<m; ++i){
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        indegree[b]++; // a->b: b로 들어오는 간선이 1개 생김
    }

    // 들어오는 간선이 없는 노드에서 시작
    for(int i=1; i<=n; ++i){
        if(indegree[i]==0) q.push(i);
    }

    while(!q.empty()){
        int node = q.front();
        q.pop();
        
        cout << node << " ";
        
        // node에 연결된 노드들 간선 처리
        for(auto e : edges[node]){
            indegree[e]--;
            if(indegree[e]==0) q.push(e);
        }
    }

    return 0;
}