Tree
4 - K · BOJ 13244 · 시간 2 초 · 메모리 512 MB
One of the most important data structures in computer science is the tree. You already dealt with binary trees in the qualification round. This problem is about general trees.
Trees are the subset of graphs that have the following 3 properties:
- It is connected: for every node you can reach every other node following edges.
- If an edge is removed, the graph is no longer connected. That is, some nodes cannot be reached anymore.
- When an edge is added between two existing nodes A and B, a cycle is created. There is a cycle if there is more than one way to go from A to B.
Your task is to decide if a given graph is a tree or not.
The first line will contain an integer T representing the number of graphs to check. There will be at most 10 graphs in each test case.
Each of the graph will be represented as follows:
The first line will contain an integer N with the number of nodes in the graph. The number of nodes will be between 1 and 1,000. The identifier of each node will be an integer from 1 to N.
The next line will contain an integer M with the number of edges in the graph. There will be at most 106 edges.
The next M lines will contain 2 integers A and B each. These are the two nodes connected by an edge.
The total sum of M in all test cases is at most 106.
For each graph, a single line with “tree” if the graph represents a tree or “graph“ otherwise.
테스트 케이스
2 4 3 2 1 3 4 1 3 3 3 1 2 1 2 3 2
tree graph
2 7 5 7 2 2 4 4 3 5 6 6 1 7 6 7 2 2 4 4 3 4 5 6 5 1 6
graph tree
브라우저가 직접 호출합니다. 요청 대상: http://localhost:12010/judge
코딩살구클럽채점서버 레포를 클론한 후 채점서버를 실행하고, IP 입력란에 현재 PC의 IP를, 포트 입력란에 채점서버 포트를 등록하면 로컬 채점서버와 코딩살구클럽이 연동됩니다.
현재는 크롬브라우저만 지원합니다.
- 예시: IP
192.168.22.222, 포트12010
$ ipconfig getifaddr en0> ipconfig | findstr IPv4해설 코드
해설 코드를 보려면 버튼을 눌러주세요.