프밍노트

https://school.programmers.co.kr/learn/courses/30/lessons/258711

문제가 길다

간단 하게 설명하자면

그래프들은 1개이상의 정점과 정점들을 연결하는 단방향 간선 으로 이루어져 있다.

위 처럼 도넛 모양 그래프 막대모양 그래프 8자모양 그래프가 여러가지 있다.

그래프들과 무관한 정점을 하나 생성한뒤 그래프들을  임의의정점 하나로 향하는 간선들을 연결하였다.

그후 각 정점에 서로 다른 번호를 매겼다.

생성한 정점의 번호와 정점을 생성하기전 그래프들의 수를 구해야 한다.

return [생성한 정점의 번호, 도넛모양 그래프수,막대모양 그래푸수,8자모양그래프수]

해당 문제의 입출력 예제를 보자면

1번 = 도넛모양

4->3 = 막대모양 그래프

2 = 임의의 정점 

그럼으로 return [2,1,1,0]

정점들을 탐색하며 노느들이 해당하는 정보를 알면되는 간단한 문제다.

간선은 단방향 단선뿐이며,  

노느들의 특징은

도넛모양은 시작위치에서 모든 노드들을 한번씩 거친후 다시 첫 노드로 돌아온다는것이다.

단방향노드는 마지막노드까지 탐색후 끝난다.

8자모양 그래프는 시작노드로 오기전 중간노드를 거친후 돌아온다

도넛모양과 유사하지만 같은노드를 다시 만났을때 처음 시작한 노드가 아니라는 점이 다르다.

해당문제는 시작 노드와 간선들의 특징만 생각하면 어렵지않다.

map 에 정점과 간선들을 추가해주면서

특징들을 확인하기위해 

간선이 나가는 횟수와

자신을 가리키는 간선이 있는지 확인한다 

	unordered_map<int, vector<int>> map;
for (auto e : edges) {
		map[e[0]].push_back(e[1]);
		edin[e[0]]++;
		Bedin[e[1]] = true;
	}

 간선이 나가는 수를 저장했던 edin을 반복하면 노드들을 전부 탐색한다

제일크며 Bedin로 나에게 도착했던간선이 없는 노드를 찾으면

시작부분일것이다

단방향 간선이 존재하기에 간선수를 추가로 확인했다.

	int s = 0;
	for (auto i : edin) {
		if (s < i.second && !Bedin[i.first])
		{
			s = i.second;
			start_N = i.first;
		}
	}
	answer[0] = start_N;

시작 노드에서 나가는 그래프들을 전부 돌면서 무슨 그래프인지만 알아내면 된다.

	for (auto num : map[start_N]) {
		star = num;
		answer[Solution_find(map, num)]++;
	}

만약  현재노드의간선이 없다면? 직선 2번

다시도착한게 size가 1이상이면 8번

다음 간선이 start 까지 도착했다면 도넛모양

다음노드 탐색

int Solution_find(unordered_map<int, vector<int>>& m, int num) {
	if (m[num].size() > 1)return 3;
	if ((m[num].size() == 0)) return 2;
	if (m[num][0] == star) return 1;
	for (int i = 0; i < m[num].size(); i++)
		return Solution_find(m, m[num][i]);
}

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

using namespace std;
int star = 0;
int Solution_find(unordered_map<int, vector<int>>& m, int num) {
	if (m[num].size() > 1)return 3;
	if ((m[num].size() == 0)) return 2;
	if (m[num][0] == star) return 1;
	for (int i = 0; i < m[num].size(); i++)
		return Solution_find(m, m[num][i]);
}

vector<int> solution(vector<vector<int>> edges) {

	vector<int> answer(4);

	unordered_map<int,int> edin;
	unordered_map<int,bool> Bedin;
	int start_N = 0;
	unordered_map<int, vector<int>> map;
	for (auto e : edges) {
		map[e[0]].push_back(e[1]);
		edin[e[0]]++;
		Bedin[e[1]] = true;
	}
	int s = 0;
	for (auto i : edin) {
		if (s < i.second && !Bedin[i.first])
		{
			s = i.second;
			start_N = i.first;
		}
	}
	answer[0] = start_N;

	for (auto num : map[start_N]) {
		star = num;
		answer[Solution_find(map, num)]++;
	}


	return answer;
}