글 읽기 - 반례 부탁드립니다

dk10211 3년 전 0

d[]라는 배열에 진입차수를 저장하여 d[i] 배열의 값이 0이된다면 lt[i]만들 수 있다 라고 가정하여 풀었습니다.

그리고 한 물약이 진입차수를 두 번 뺄 것을 우려하여 set에 넣어보고 삽입 성공일때에만 해당 물약을 사용하는 레시피들의 진입차수를 1씩 깎아 주었는데 어디가 틀렸는지 도저히 모르겠습니다..

#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
vector<int>v[200005];
int d[200005];
int lt[200005];
set<int>s;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int k;
		cin >> k;
		d[i] = k;
		while (k--) {
			int x;
			cin >> x;
			v[x].push_back(i);
		}
		cin >> k;
		lt[i] = k;
	}
	int k;
	cin >> k;
	queue<int>q;
	pair<set<int>::iterator, bool>pr;
	while (k--) {
		int x;
		cin >> x;
		s.insert(x);
		for (unsigned int i = 0; i < v[x].size(); i++) {
			int y = v[x][i];
			if (--d[y] == 0) {
				pr = s.insert(lt[y]);
				if (pr.second) q.push(lt[y]);
			}
		}
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (unsigned int i = 0; i < v[x].size(); i++) {
			int y = v[x][i];
			if (--d[y] == 0) {
				pr = s.insert(lt[y]);
				if (pr.second) q.push(lt[y]);
			}
		}
	}
	cout << s.size() << "\n";
	for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << " ";
}

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

문제

문제

출처

ICPC

반례 부탁드립니다

dk10211 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말