인프런 커뮤니티 질문&답변

트리는 노드와 노드 사이 간선이 하나 인 것으로 알고 있습니다.

//이게 왜 필요하죠? 라고 물으신 부분은

예제 입력 1번의 두 번째 테스트 케이스가 노드1 과 노드2 사이 간선이 2개이고 그 결과 그래프가 되어서

이미 노드와 노드 사이 간선이 있다면 트리가 불가능 하다고 작성한 로직입니다.

이러한 로직이 전체 코드를 놓고 봤을 때 m=n-1을 의미 하는 것 아닌가요?

음..

엣지가 있는 체크한다. 이 부분 설명 부탁드려도 될까요?

그리고 주석달았습니다. 확인부탁드려요

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>

using namespace std;

int T,n,m,possible;
int a, b;
vector<int> adj[1004];
int visited[1004];

void dfs(int here)
{
	visited[here] = 1;

	for (int there : adj[here])
	{
		if (visited[there] == 0)
		{
			dfs(there);
		}
	}
}


int main()
{
	cin >> T;

	while (T--)
	{
		// initialize good 
		possible = 1;
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i < 1004; i++)
		{
			adj[i].clear();
		}

		cin >> n;
		cin >> m;

		// make map
		for(int i = 0; i < m; i++)
		{
			cin >> a >> b;
			//이게 왜 필요하죠? 
			auto it = find(adj[a].begin(), adj[a].end(), b);
			if (it != adj[a].end())
			{
				possible = 0;
				break;
			}
			else
			{
				adj[a].push_back(b);
				adj[b].push_back(a);
			}
		}

		//dfs 굿 
		dfs(1);

		// check
		for (int i = 1; i <= n; i++)
		{
			if (visited[i] == 0)
			{
				possible = 0;
				break;
			}
		}
		//m = n - 1을 확인하는 부분이 없네요? 
		// print
		if (possible == 1) cout << "tree" << "\n";
		else cout << "graph" << "\n";
	}

	return 0;
}