백준 [C++] 13244 Tree

<조건 분석>

1. 노드의 갯수는 최대 1000개 인데, 트리의 특징을 사용하는 것이므로 크게 조건에 연연하지 않아도 될 것 같음.

 

<문제 해결 포인트>

1. 트리의 특징 2가지를 알면 되는 문제였음.

 

2. Edge(간선) = N(노드) - 1 와 모두 연결되어 있는것임.(DFS 한번으로 모두 탐색 가능)

 

#include <bits/stdc++.h>
using namespace std;

int t, n, m;
int visited[1000];
vector<vector<int>> v;

void DFS(int start)
{
    visited[start] = 1;

    for (auto item : v[start])
    {
        if (visited[item]) continue;

        DFS(item);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;

    while (t--)
    {
        ::memset(visited, 0, sizeof(visited));
        v.clear(); v.resize(1004);
        int cnt = 0;
        cin >> n >> m;

        for (int i = 0; i < m; i++)
        {
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
        }

        for (int i = 1; i <= n; i++)
        {
            if (visited[i]) continue;
            DFS(i);
            cnt++;
        }

        if (m == n - 1 && cnt == 1) cout << "tree" << "\n";
        else cout << "graph" << "\n";
    }
}