위상정렬 개념

1. 위상정렬은 비순환 방향 그래프이다.(사이클 X)
2. 정점을 선형으로 정렬
3. 사례) 선수과목
4. 인접리스트 사용시 시간복잡도 O(V+E)

내가 시도한 방법

1. 시작점을 찾기 위해 Reverse(child->parent로 가는 인접 리스트를 하나 만들어줌
2. 이 후 size()인 V가 시작점으로 저장
3. q에 시작점을 담은 후 제거
4. 이 후 chk bool 배열을 사용해 reverseAdj리스트에서 해당 노드가 빠져나가면 chk해줌,,
5. 이 후 하나라도 노드가 check가 안되어있으면 다음과정 진행 불가
6. 이후 인접리스트에서 노드 queue에 저장.

틀린 이유

1. 위의 5번까지는 맞지만 6번에서도 해당 노드의 바로 이전 자식노드들이 전부 선행완료가되면 그때 queue에 집어넣어야되는데 바로 queue에 집어넣어 문제 발생(이렇게되면 중복이 생긴다)
2. 또한 현재 방법은 reverseAdj에서 인접리스트를 직접 세고 지우고 해야하는데 이러면 시간복잡도가 더 듬..

vector<int> adj[1001];
vector<int> reverseAdj[1001];
bool chk[1001];
queue<int> q;
vector<int> solution(int V, int E)
{
	vector<int> ans;
	//find Start
	for (int i = 1; i <= V; i++)
	{
		if (reverseAdj[i].size() == 0) {
			q.push(i);
		}
	}
	while (!q.empty())
	{
		int id = q.front();
		q.pop();
		ans.push_back(id);
		chk[id] = true;
		bool chkId = true;
		for (int i = 0; i < reverseAdj[id].size(); i++)
		{
			if (!chk[reverseAdj[id][i]])
			{
				chkId = false;
			}
		}
		if (!chkId) continue;
		for (int i = 0; i < adj[id].size(); i++)
		{
				q.push(adj[id][i]);
		}
	}
	return ans;
}

해결방법

1. q에 넣어야할 노드의 선행 개수를 파악하는것이 중요★
   size()==0을 계산해서?? 할수도있지만 erase, push_back은 시간복잡도가 너무 든다.
2. 따라서 degree배열을 생성해서 간접리스트에서 end를 pushback할때 동시에 degree를 증가
   (카운드하는배열로생각-> 이전노드가 몇개있는가???)
3. 이 후 degree를 감소시켜주면서 degree==0일경우만 queue에 집어넣는다.(이전 노드처리를 다 했다는 뜻)

vector<int> solution(int V, int E)
{
	vector<int> ans;
	//find Start
	for (int i = 1; i <= V; i++)
	{
		if (degree[i] == 0) {
			q.push(i);
		}
	}
	while (!q.empty())
	{
		int id = q.front();
		q.pop();
		ans.push_back(id);
		for (int i = 0; i < adj[id].size(); i++)
		{
			degree[adj[id][i]] -= 1;
			if (degree[adj[id][i]] == 0)
			{
				q.push(adj[id][i]);
			}
		}
	}
	return ans;
}