[ BOJ / C++ ] 13244번 : Tree

[ BOJ ] 13244번 : Tree

문제 : https://www.acmicpc.net/problem/13244

---

[  문제  ]

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:

 

1. It is connected: for every node you can reach every other node following edges.
2. If an edge is removed, the graph is no longer connected. That is, some nodes cannot be reached anymore.
3. 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.

 

컴퓨터 과학에서 가장 중요한 자료 구조 중 하나는 트리입니다. 

예선전에서 이미 이진 트리를 다루었습니다. 이 문제는 일반적인 트리에 관한 것입니다.

트리는 다음 세 가지 속성을 가진 그래프의 부분 집합입니다.

1. 연결되어 있습니다. 모든 노드에서 간선을 따라 다른 모든 노드에 도달할 수 있습니다.
2. 간선이 제거되면 그래프는 더 이상 연결되지 않습니다. 즉, 일부 노드에 더 이상 도달할 수 없습니다.
3. 두 기존 노드 A와 B 사이에 간선이 추가되면 사이클이 생성됩니다. A에서 B로 이동하는 방법이 두 가지 이상인 경우 사이클이 존재합니다.

주어진 그래프가 트리인지 아닌지 판단하는 것이 과제입니다.

[  입력  ]

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 $10^{6}$ 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 $10^{6}$.

 

첫 번째 줄에는 검사할 그래프의 수를 나타내는 정수 T가 주어진다. 각 테스트 케이스에는 최대 10개의 그래프가 포함된다.

각 그래프는 다음과 같은 형식으로 주어진다:

첫 번째 줄에는 그래프의 노드 수를 나타내는 정수 N이 주어진다. 노드의 수는 1 이상 1,000 이하이다. 각 노드의 식별자는 1부터 N까지의 정수이다.

다음 줄에는 그래프의 간선 수를 나타내는 정수 M이 주어진다. 간선의 수는 최대 $10^{6}$개이다.

다음 M개의 줄에는 각각 두 개의 정수 A와 B가 주어진다. 이는 노드 A와 노드 B가 간선으로 연결되어 있다는 의미이다.

모든 테스트 케이스에서 M의 총합은 최대 $10^{6}$개이다.

 

[  출력  ]

For each graph, a single line with “tree” if the graph represents a tree or “graph“ otherwise.

 

각 그래프에 대해, 해당 그래프가 트리를 나타내면 'tree'를, 그렇지 않으면 'graph'를 한 줄에 출력하세요.

---

[  문제 접근 및 풀이  ]

트리의 간선은 무조건 (노드 개수 - 1) 개이다.

따라서 M이 N-1개가 아니라면 먼저 graph를 출력 후 종료하였고

간선이 N-1개일 경우 모두 양방향으로 입력하고 노드 하나를 집어넣어

연결되어 있는 모든 정점을 지나며 방문 처리를 한다.

이후 1~N까지 모든 정점에 대해서 방문 처리가 하나라도 되어있지 않다면

graph를, 방문 처리가 됐다면 tree를 출력했다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
void Q_13244();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        Q_13244();
    }
}
void Q_13244(){
    int N,M;
    cin >> N >> M;
    vector<int> V[1001];
    for(int i=0;i<M;i++){
        int a,b;
        cin >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    if(M!=N-1) {
        cout << "graph"<<"\n";
        return;
    }
    queue<int> q;
    q.push(1);
    bool vis[1001]={false,};
    vis[1]=true;
    while(!q.empty()){
        auto cur=q.front(); q.pop();
        for(auto x:V[cur]){
            if(vis[x])continue;
            vis[x]=true;
            q.push(x);
        }
    }
    for(int i=1;i<=N;i++){
        if(!vis[i]) {
            cout << "graph\n";
            return;
        }
    }
    cout <<"tree\n";
}

---