글 읽기 - c++ 어느 부분이 잘못되었는지 봐주시면 감사하겠습니다.

sjh04196 1년 전 0

어느 부분이 잘못되었을까요ㅠㅠ

고수님들의 도움이 필요합니다..

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <memory.h>
#include <set>
#include <string.h>

using namespace std;
using std::fill;
bool visit[1000] = {false};
void dfs(int num, vector<vector<int>> g, int cnt);
void result(int num,int cnt,int count);
vector<int> ans;
int tree_count[1000];

int d, edge;
int count = 0;
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    do
    {
        vector<vector<int>> graph(1000); // 2중벡터사용
        cin >> d >> edge;
        count++;

        if (d == 0 && edge == 0)
        {
            break;
        };

        for (int i = 0; i < edge; i++)
        {
            int x, y;
            cin >> x >> y;
            graph[x].push_back(y);
            graph[y].push_back(x);
        };

        memset(visit, false, 1000);

        dfs(1, graph,count);


    } while (d != 0 && edge != 0);

    int c = 0;

    for (int i = 0; i < ans.size();i++){
        c++;
        int temp = ans[i];
        result(temp, c ,tree_count[c]);
    };
};

void dfs(int num, vector<vector<int>> graph,int count)
{
    queue<int> q;
    stack<int> s;
    bool sub = false;
    int cnt = 0;
    q.push(num);

    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        visit[now] = true;
        s.push(now);

        for (int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i];

            // cout << "s.top: " << s.top() << endl;
            // cout << "next:" << next << endl;
            // s.push(next);
            if (!visit[next])
            {
                // visit[next] = true;
                q.push(next);
                cnt++;
            };
        };
    };
    int s_size = s.size();
    set<int> check;
    while (!s.empty())
    {
        check.insert(s.top());
        s.pop();
    };

    if (s_size != check.size())
    {
        ans.push_back(1);
    }
    else if (cnt == d - 1)
    {
        ans.push_back(2);
    }
    else if (d > cnt)
    {
        ans.push_back(3);
        tree_count[count] = cnt;
    };

}

void result(int num,int cnt,int count){
    if (num==1){
        cout << "Case " << cnt << ": " << "No trees." << endl;
    };
    if (num==2){
        cout << "Case " << cnt << ": " << "There is one tree." << endl;
    };
    if (num==3){
        cout << "Case " << cnt << ": "<< "A forest of " << count << " trees." << endl;
    }
}

pill27211 1년 전 1

그래프가 2개 이상 떨어져 있는 경우도 생각해야 합니다.

Input)

6 6
1 2
1 3
4 1
2 3
3 4
6 5
0 0

Output)

Case 1: No trees.

Answer)

Case 1: There is one tree.

sjh04196 1년 전 0

안녕하세요 고수님

답변 달아 주셔서 감사합니다!

제가 모든 정점에서 탐색해서 트리 갯수를 세주어야 하는 걸 놓친거 같습니다.

그래서 모든 정점에서 탐색해서 트리 갯수를 세주는 조건으로

코드를 고쳤는데 ..틀렸습니다 라고 뜨네요..

어떤 부분이 잘못되었는지 알려주시면 감사하겠습니다 ㅠㅠ

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <memory.h>
#include <set>
#include <string.h>

/*트리 문제 채점 16% 틀림

질문에서 반례 참고해서 수정해야함*/

using namespace std;
using std::fill;
bool visit[1000] = {false};
// vector<vector<int>> graph(1000); //2중벡터사용
void dfs(int num, vector<vector<int>> g, int cnt);
void result(int num,int cnt,int count);
vector<int> ans;
int tree_count[1000];

int d, edge;
int count = 0;
int tree;
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    do
    {
        vector<vector<int>> graph(1000); // 2중벡터사용
        cin >> d >> edge;
        count++;
        tree = 0;
        int answer = 0;

        if (d == 0 && edge == 0)
        {
            break;
        };

        for (int i = 0; i < edge; i++)
        {
            int x, y;
            cin >> x >> y;
            graph[x].push_back(y);
            graph[y].push_back(x);
        };

        memset(visit, false, 1000);

        for (int i = 1; i <= d;i++)
        {
            dfs(i, graph, count);
            memset(visit, false, 1000);
        };

        answer = tree - 1;
        if(answer==d-1 || answer==1){
            ans.push_back(2);
        }else if(answer==-1){
            ans.push_back(1);
        }else{
            ans.push_back(3);
        }

    } while (d != 0 && edge != 0);

    

    int c = 0;

    for (int i = 0; i < ans.size();i++){
        c++;
        int temp = ans[i];
        result(temp, c ,tree_count[c]);
    };
};

void dfs(int num, vector<vector<int>> graph,int count)
{
    queue<int> q;
    stack<int> s;
    bool sub = false;
    int cnt = 0;
    q.push(num);

    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        visit[now] = true;
        s.push(now);

        if(graph[now].size()==0){ // 연결이 없는 정점은 돌 필요 x
            return;
        };

        for (int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i];

            // cout << "s.top: " << s.top() << endl;
            //s.push(next);
            if (!visit[next])
            {
                // visit[next] = true;
                q.push(next);

                cnt++;
            };
        };
    };
    int s_size = s.size();
    set<int> check;
    while (!s.empty())
    {
        check.insert(s.top());
        s.pop();
    };

    if(s_size == check.size()){ // 중복이 없으면
        tree++;
    };

    tree_count[count] = tree - 1;
}

void result(int num,int cnt,int count){
    if (num==1){
        cout << "Case " << cnt << ": " << "No trees." << endl;
    };
    if (num==2){
        cout << "Case " << cnt << ": " << "There is one tree." << endl;
    };
    if (num==3){
        cout << "Case " << cnt << ": "<< "A forest of " << count << " trees." << endl;
    }
}

pill27211 1년 전 0

https://www.acmicpc.net/board/...

사이클이 발생해도 해당 그래프안에 트리가 존재할 수 있습니다.

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

문제

문제

출처

ICPC

c++ 어느 부분이 잘못되었는지 봐주시면 감사하겠습니다.

sjh04196 1년 전 0

pill27211 1년 전 1

sjh04196 1년 전 0

pill27211 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말