글 읽기 - 반례를 못찾겠습니다 ㅠ

mdm 3년 전 0

dag로 하면 맞았습니다! 가 되는데

제가 처음에 푼 방식으로 하면 틀리는 이유를 못찾겠습니다.

틀린 이유를 알려주시면 감사하겠습니다!.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int, int> pint;
typedef long long ll;
const int N = 100010;
vector<int> adj[32010];
int siz[N];
int dfs(int h) {
	if (siz[h])return siz[h];
	int s = 1;
	for (int t : adj[h]) 
		s += dfs(t);
	
	return siz[h] = s;
}
bool great(int &a, int &b) {
	return siz[a] > siz[b];
}
int main() {
	ios::sync_with_stdio(false); std::cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
	}
	vector<int> ar;
	for (int i = 1; i <= n; ++i) {
		ar.push_back(i);
		if (!siz[i])
			dfs(i);
	}

	sort(ar.begin(), ar.end(), great);
	for (int v : ar)
		cout << v << " ";
		


}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다 ㅠ

mdm 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말