글 읽기 - [C++] 반례가 뭐가 있을까요..?

5stralia 5년 전 0

양방향, 방문 노드 점검 모두 하고 여러 반례들을 돌려봤는데 틀렸다고 뜹니다

코드 점검 좀 부탁드려요

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

int main() {
	int n, p;
	int count = 0;
	scanf("%d", &n);
	scanf("%d", &p);
	vector<int> *com = new vector<int>[n + 1];
	for (int i = 0; i < p; i++) {
		int src, dst;
		scanf("%d %d", &src, &dst);
		com[src].push_back(dst);
		com[dst].push_back(src);
	}

	bool *visit = new bool[n + 1]{ 0, 1, 0 };
	stack<int> st;
	vector<int>::iterator it;
	for (it = com[1].begin(); it != com[1].end();it++) {
		st.push(*it);
		visit[*it] = 1;
	}

	while (!st.empty()) {
		int cur = st.top();
		st.pop();
		if (cur == 1) continue;
		visit[cur] = 1;
		count++;
		for (it = com[cur].begin(); it != com[cur].end(); it++) {
			if (visit[*it])	continue;
			st.push(*it);
		}
	}
	
	printf("%d", count);
	
	return 0;
}

hhs250 5년 전 1

반례

7 7

1 2

2 3

1 5

5 2

5 6

4 7

4가 나와야하는데 5가 나오네요.

중복에 대한 처리가 필요합니다.

5stralia 5년 전 0

@hhs205

조언에 따라 중복 처리를 했는데 또 틀렸습니다 뜨네요

위 코드의 그래프를 구성하는 for문에서 처리했는데 잘못 처리를 한걸까요?

for (int i = 0; i < p; i++) {
		int src, dst;
		scanf("%d %d", &src, &dst);
    
        // 중복처리
		it = find(com[src].begin(), com[src].end(), dst); 
		if (it != com[src].end()) continue;
    
		com[src].push_back(dst);
		com[dst].push_back(src);
	}

hhs250 5년 전 1

이렇게 짜면 통과가 되네요

참고하세요~

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

int main() {
	int n, p;
	int count = 0;
	scanf("%d", &n);
	scanf("%d", &p);
	vector<int> *com = new vector<int>[n + 1];
	for (int i = 0; i < p; i++) {
		int src, dst;
		scanf("%d %d", &src, &dst);
		com[src].push_back(dst);
		com[dst].push_back(src);
	}

	bool *visit = new bool[n + 1]{ 0, 1, 0 };
	stack<int> st;
	vector<int>::iterator it;
	for (it = com[1].begin(); it != com[1].end(); it++) {
		st.push(*it);
		//visit[*it] = 1;
	}

	while (!st.empty()) {
		int cur = st.top();
		st.pop();
		if (cur == 1) continue;
		if(!visit[cur])
		{
			visit[cur] = 1;
			count++;
		}		
		for (it = com[cur].begin(); it != com[cur].end(); it++) {
			if (visit[*it])	continue;
			st.push(*it);
		}
	}

	printf("%d", count);

	return 0;
}

5stralia 5년 전 1

@hhs250

스택에 넣을 때 방문 표시를 하다가 while문 안에서는 꺼낼 때 방문 표시를 한 부분이 문제였네요

감사합니다 덕분에 문제를 알았습니다

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

문제

문제

출처

ICPC

[C++] 반례가 뭐가 있을까요..?

5stralia 5년 전 0

hhs250 5년 전 1

5stralia 5년 전 0

hhs250 5년 전 1

5stralia 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말