글 읽기 - 도아주십쇼

ldhun041203 2년 전 0

Back edge를 체크하는 방식으로 cycle을 확인해서 Tree의 개수를 늘리는 방식으로 풀려는데.

Back edge로 풀면 안되는 걸 까요?

#include <iostream>

#include <algorithm>
#include <string>
#include <cstring>
#include <memory>
#include <cmath>

//data structure
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <set>
#include <list>
#include <tuple>

#define INF 987654321
#define MAX
#define X first
#define Y second

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;

//--------struct,class-area



//---------variable-area

int N, M, T;
int visit[501], check[501];
vector <int> adj[501];


//---------function-area

int dfs(int i) {
    visit[i] = 1;

    int ret = 0;
    for (auto j : adj[i]) {
        if (!visit[j])
            ret = dfs(j) | ret;
        else if (!check[j])
            ret = 1;
    }

    check[i] = 1;
    return ret;
}

//---------end

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

//----------start

    while(true) {
        memset(visit,0,sizeof(visit));
        memset(check,0,sizeof(check));
        for (int i = 1; i <= 500; i++) adj[i].clear();
        T = 0;

        cin >> N >> M;

        if (N == 0 && M == 0) break;

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

        for (int i = 1; i <= N; i++)
            if(!visit[i])
                if(!dfs(i))
                    T++;


        if (T == 0) {
            cout << "No trees.\n";
        } else if (T == 1) {
            cout << "There is one tree.\n";
        } else {
            cout << "A forest of " << T << " trees.\n";
        }
    }



//-----------end

    return 0;
}

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

문제

문제

출처

ICPC

도아주십쇼

ldhun041203 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말