백준 - 4803 트리

문제 링크입니다 : https://www.acmicpc.net/problem/4803

4803번: 트리

 

 

트리의 기본 조건 : 사이클이 없다.

사이클이 있는지 없는지 조사하는 문제였다.

 

 

 

 

 

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<vector<int>> adj;
vector<bool> visited;
vector<bool> visiting;


bool hasCycle(int prev, int here) {
    if(visiting[here]) return true;
    if(visited[here]) return false;
    visited[here] = true;
    visiting[here] = true;
    for(int i = 0; i < adj[here].size(); i++) {
        if(adj[here][i] == prev) continue;
        if(hasCycle(here, adj[here][i])) return true;
    }
    visiting[here] = false;
    return false;
}

int main() {
    int testCase = 0;
    while(true) {
        testCase++;
        int treeNum = 0;

        cin >> N >> M;
        if(N == 0 && M == 0) break;
        adj.assign(N + 1, vector<int>());
        visited.assign(N + 1, false);
        visiting.assign(N + 1, false);

        int u, v;
        for(int i = 0; i < M; i++) {
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }


        for(int i = 1; i <= N; i++) {
            if(!visited[i] && !hasCycle(0, i)) {
                treeNum++;
            }
        }

        cout << "Case " << testCase << ": ";
        if(treeNum > 1) {
            cout << "A forest of " << treeNum << " trees.\n";
        } else if(treeNum == 1) {
            cout << "There is one tree.\n";
        } else {
            cout << "No trees.\n";
        }

    }

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~