[백준] 13244번 Tree C++ 코드

코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
bool cycle = false;
int t,n,m,a,b,visited[1004];
vector<int> adj[1004];
void FASTIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}

void dfs(int x) {
  visited[x] = 1;
  for(int i : adj[x]) {
    if(!visited[i]) dfs(i);
  }
}

int main() {
  FASTIO();
  cin >> t;
  string res;
  while(t--) {
    for(int i =0; i < 1004; i++) adj[i].clear();
    int cnt = 0;
    cin >> n;
    cin >> m;
    for(int i = 0; i < m; i++) {
      cin >> a >> b;
      adj[a].push_back(b);
      adj[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) {
      if(!visited[i]){
        dfs(i);
        cnt++;
      }
    }
    if(cnt == 1 && m+1 == n) cout << "tree" << '\n';
    else cout << "graph" << '\n';
    memset(visited,0,sizeof(visited));
  }
  return 0;
}

1번에서 출발해 모든 정점을 한 번에 방문하고, 간선의 개수가 노드 - 1을 동시에 만족하면 트리, 아니면 그래프이다.