글 읽기 - 트리 조건 질문있습니다.

fhkfrdnfrrnfr001 2년 전 0

이미 방문한 경우에 다시 방문하는 경우 트리가 아닌 걸로 처리해봤는데

이게 왜 안될까요?

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
#include <memory.h>
#include <iomanip>
#include <list>
#include <unordered_map>        // map대신 이거쓰자 지도 관련 문제 풀때 변수명을 map이라고 못지음
#include <set>
#include <stack>

using namespace std;

template<typename TKey, typename TValue>
using umap = unordered_map<TKey, TValue>;

#define ll long long
#define ull unsigned ll

int vertex_count;
int edge_count;
bool visit[501];
int tc = 0;
vector<int> tree[501];

void solve() {
    for(;;) {
        cin >> vertex_count >> edge_count;

        if (vertex_count == 0 && edge_count == 0) {
            break;
        }

        for (int i = 0; i < edge_count; ++i) {
            int v1;
            int v2;

            cin >> v1 >> v2;
            tree[v1].push_back(v2);
        }

        queue<int> bfs_queue;
        int tree_cnt = 0;

        for (int i = 1; i <= vertex_count; ++i) {
	        if (visit[i] == false) {
                bfs_queue.push(i);
                visit[i] = true;

                bool is_tree = true;
                while (!bfs_queue.empty()) {
                    int cur = bfs_queue.front();
                    bfs_queue.pop();

                    
                    
                    for (auto& next : tree[cur]) {

                        // 이미 방문한 경우 진입 차수가 2개 이상이라는 의미이므로 트리가 아닌 그래프이다.
                        // 또는 싸이클을 이룬 것일 수도 있음
	                    if (visit[next]) {
                            is_tree = false;
                            continue;
	                    }

                        visit[next] = true;
                        bfs_queue.push(next);
                    }
                }

                if (is_tree) {
                    tree_cnt++;
                }
	        }
        }

        if (tree_cnt == 1) {
            printf("Case %d: There is one tree.\n", ++tc);
        } else if (tree_cnt == 0) {
            printf("Case %d: No trees.\n", ++tc);
        } else {
            printf("Case %d: A forest of %d trees.\n", ++tc, tree_cnt);
        }

        for (int i = 1; i <= vertex_count; ++i) {
            tree[i].clear();
        }

        fill_n(visit + 1, vertex_count, false);
    }


}

int main() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

fhkfrdnfrrnfr001 2년 전 0

무방향 그래프였네요 ㅠㅠ

해결했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

트리 조건 질문있습니다.

fhkfrdnfrrnfr001 2년 전 0

fhkfrdnfrrnfr001 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말