글 읽기 - 2606 반례 질문입니다

fere1032 1년 전 0

반례 다 찾아서 돌려봤는데 맞게 나왔습니다.

근데 제출하면 틀리네요..

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int num, pairs, counts;
bool *notVisited;

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

	cin >> num >> pairs;
	notVisited = new bool[num+1];
	int from, to;
	vector<vector<int>> graph(num+1);

	for (int i = 0; i < pairs; i++)
	{
		cin >> from >> to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}

	queue<int> q;
	q.push(1);
	notVisited[1] = false;

	while (!q.empty())
	{
		int f = q.front();
		q.pop();

		for (int i = 0; i < graph[f].size(); i++)
			if (notVisited[graph[f][i]])
			{
				notVisited[graph[f][i]] = false;
				q.push(graph[f][i]);
				counts++;
			}
	}

	cout << counts;

	return 0;
}

seawon0808 1년 전 0

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

반례를 다 찾아서 안 돌리신 것 같은데요.

이 글은 작성자 님이 글을 쓰시기 전에 위에서 3번째에 있던 글입니다.

fere1032 1년 전 0

6 출력 잘 되는것 같은데요

adung7 1년 전 1

notvisited 포인터를 써서 동적할당을 하셨는데 여기서 notvisited가 가리키는 데이터들은 초기화 하지 않았으므로 쓰레기값이고 예상할수 없는 값입니다 따라서 계산결과가 다르게 나올수있습니다

이를 수정해주시고 마지막에 delete[] 연산으로 메모리 해제를 해주세요 해당 부분 고치시면 AC받으실수 있습니다

또 하나 첨언을 하자면 방문배열 사용하실때 vector<bool>을 사용하시는게 좀 더 깔끔하지 않을까 생각됩니다

fere1032 1년 전 0

바로 해결되었습니다 감사합니다!

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