(4803) 트리

https://www.acmicpc.net/problem/4803

단계별로 풀어보기

33단계(트리) 7번째

 

 

 

트리 여부를 확인하는 문제. 그래프를 순회하면서 이전 정점이 아니고 이미 방문한 정점과 이어져 있다면 사이클이 있다는 것이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

void solve(int c, int n, int m){
  vector adj(n+1, vector<int> ());
  vector<bool> visited(n+1);
  int cnt= 0;
  bool istree= true;
  
  while(m--){
    int u, v;
    
    cin >> u >> v;
    
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  auto dfs= [&](auto self, int now, int prev) -> void {
    visited[now]= true;
    
    for(int next:adj[now]){
      if(next==prev)  continue;
      if(visited[next]){
        istree= false;
        continue;
      }
      
      self(self, next, now);
    }
  };
  
  for(int i=1;i<=n;i++){
    if(visited[i])  continue;
    
    istree= true;
    dfs(dfs, i, 0);
    cnt+= istree;
  }
  
  cout << "Case " << c << ": ";
  
  if(cnt==0)  cout << "No trees.\n";
  else if(cnt==1)  cout << "There is one tree.\n";
  else  cout << "A forest of " << cnt << " trees.\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  for(int i=1;;i++){
    int n, m;
    
    cin >> n >> m;
    
    if(!n)  break;
    
    solve(i, n, m);
  }
  
  return 0;
}