글 읽기 - 왜 틀렸을까요?

ckdtjs505 5년 전 0

왜틀렸을까요? .....

최소의 경우 최대의 경우 다 따져봤는데도 잘 모르겠습니다ㅠ

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

bool check[1000] = {0};
using namespace std;
int main (){
	int n, m; cin >> n >> m;
	vector<int> p[n+1];
	for(int i = 0 ; i < m; i++){
		int u,v; cin >> u >> v;
		p[u].push_back(v);
	}
	for(int i = 0; i < p[1].size() ; i++){
		int temp = p[1][i];
		check[temp] = true;
		for(int j = 0; j <p[temp].size() ; j++){
			int temp2 = p[temp][j];
			check[temp2] = true;
		}
	}
	
	int count = 0;
	for(int i = 2; i <= n; i++){
		if(check[i]){
			count++;
		}
			
	}
		cout << count;
	
}

ckdgus2482 5년 전 1

양방향 그래프입니다

ckdtjs505 5년 전 0

ckdgus2482..

양방향 그래프로 구현해서 제출했는데.. 맞았다고 제출이 되었습니다.

하지만 여전히 저는 이해가 되지 않습니다.

왜 단방향 그래프는 틀렸는지..

저의 생각은 이렇습니다.

굳이 양방향을 할필요가 있는가?

탐색하는 방향은 정해져있지 않은가?

혹시나 반례를 알려주신다면 더욱 감사합니다

꾸벅

ckdgus2482 5년 전 1

출발점이 고정이라고 해서 탐색하는 방향이 정해져있는것은 아닙니다.

각각의 간선을 따라갈때 항상 같은 방향으로만 따라간다면 단방향 그래프로 봐도 되겠지만 이 문제는 그렇지 않습니다.

간단한 예를 들자면

2 1

3 2

이러한 입력에서 올바른 답은 2이지만

단방향 그래프로 탐색한다면 0이겠죠

mjkim1201 5년 전 0

근데 문제에 a<b라는 조건이있는데 그럼 2 1 자체가 입력이 안되지 않나요 ?

yeolpyeong 5년 전 1

10
10
4 10
7 10
3 7
6 8
1 7
1 6
1 5
1 9
2 4
3 8

단방향 그래프는 이런 경우 3번(친구의 친구)을 카운트할 수 없습니다.

1 -> 7 -> 3

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

문제

문제

출처

ICPC

왜 틀렸을까요?

ckdtjs505 5년 전 0

ckdgus2482 5년 전 1

ckdtjs505 5년 전 0

ckdgus2482 5년 전 1

mjkim1201 5년 전 0

yeolpyeong 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말