This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <vector> | |
| /** | |
| * https://www.acmicpc.net/problem/5567 | |
| * BOJ 백준온라인져지 5567 결혼식 풀이 | |
| */ | |
| using namespace std; | |
| int main () { | |
| int N = 0; | |
| scanf("%d", &N); | |
| N++; | |
| int *friends = new int[N]; | |
| int edgeLength; | |
| scanf("%d", &edgeLength); | |
| vector<pair<int, int> > edges; | |
| for (int i = 0; i < edgeLength; i++){ | |
| int s, e; | |
| scanf("%d%d", &s, &e); | |
| if (s == 1) friends[e] = 1; | |
| else if (e == 1) friends[s] = 1; | |
| else edges.push_back(make_pair(s, e)); | |
| } | |
| for (int i = 0; i < edges.size(); i++) { | |
| int s = edges[i].first; int e = edges[i].second; | |
| if (friends[s] == 1 && friends[e] == 0) friends[e] = 2; | |
| else if (friends[e] == 1 && friends[s] == 0) friends[s] = 2; | |
| } | |
| int result = 0; | |
| for (int i = 0; i < N; i++) { | |
| if (friends[i] == 1 || friends[i] == 2) result++; | |
| } | |
| printf("%d", result); | |
| } |
문제
상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai< bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.
출력
첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 백준온라인져지 10610 30 풀이 (0) | 2018.02.17 |
|---|---|
| BOJ 백준온라인져지 14487 욱제는 효도쟁이야!! 풀이 (0) | 2018.02.17 |
| BOJ 백준온라인져지 1076 저항 풀이 (0) | 2018.02.17 |
| BOJ 백준온라인져지 2010 플러그 풀이 (0) | 2018.02.17 |
| BOJ 백준온라인져지 3046 R2 풀이 (0) | 2018.02.15 |