백준 2252번: 줄 세우기 - 위상정렬 문제

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

#include <bits/stdc++.h>
using namespace std;


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n,m;
	cin >> n >> m;
	
	vector<int> graph[32001];
	vector<int> degree(n+1, 0);
	
	for(int i=0; i<m;i++){
		int a,b;
		cin >> a >> b;
		
		graph[a].push_back(b);
		degree[b]++;
	}
	
	queue<int> Q;
	
	
	for(int i=1; i<=n; i++){
		if(degree[i]==0) Q.push(i);
	}
	
	while(!Q.empty()){
		int cur = Q.front();
		Q.pop();
		cout << cur <<' ';
		
		for(int i=0; i<graph[cur].size(); i++){
			int nx = graph[cur][i];
			degree[nx]--;
			if(degree[nx]==0) Q.push(nx);	
		}
	}
		
	
}

 

처음에 아무 생각없이 32000x32000 벡터를 만들었다가

메모리 초과로 틀렸다.

그래서 32000행 벡터를 만들고 노드를 인풋 받을 때마다 push_back 해주었다.