Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2227
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2227
Airport
By OBI - Olimpíada Brasileira de Informática 2002 
Brazil
Timelimit: 1
The growing use of air transport concerns the experts who predict that congestion at airports could become a big problem in the future. The current numbers are already alarming: official reports show that in Europe, in June 2001, there was an average of 7,000 flights a day late. Concerned with the prediction of the experts in air traffic, the International Air Transport Association (ATAI) is beginning a study to find out which are the airports where air traffic might be more problematic in the future.
As a new developer hired by ATAI you have been in charge of writing a program to determine, from a list of airports and flights, which airport is more likely congestion in the future. As a measure of the probability of congestion will be used in this study the total number of flights arriving or departing from each airport.
Input
The input consists of several test sets. The first line of a test set contains two integers A (0 ≤ A ≤ 100) e V (0 ≤ V ≤ 10000), which respectively indicate the number of airports and the number of flights. Airports are identified by integers from 1 to A. The V following lines each one contains information from a flight, represented by a pair of positive integers X e Y (1 ≤ X ≠ Y ≤ A), indicating that there is an airport flight X to the airport Y. The end of the input is indicated when A = V = 0.
Output
For each entry test set your program should produce three lines. The first line identifies the test set, the form "Teste n", where n is numbered from 1. The second line should contain the airport identifier that has increased air traffic. If more than one airport has this maximum value, you must list all these airports, in ascending order of identification, and separated by at least one blank. The third line should be left blank. The spelling shown in the Output Sample below should be followed strictly.
| Input Sample | Output Sample |
|
5 7 1 3 2 1 3 2 3 4 4 5 3 5 2 5 3 5 1 3 1 2 3 2 1 2 2 1 0 0 |
Teste 1 3 Teste 2 1 2 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <:stdio.h>:
#include <:string.h>:
#define true 1
#define false 0
#define MAXSIZE 105
#define INF 0x3f3f3f3f
int voos[MAXSIZE];
int main (void)
{
int i;
int x, y;
int n, m, teste = 0;
while (scanf("%d %d", &n, &m), m && n)
{
for (i = 0; i < m; ++i)
scanf("%d %d", &x, &y), voos[x]++, voos[y]++;
int pos;
int maior = -INF;
printf("Teste %d\n", ++teste);
for (i = 1; i < = n; ++i)
if (voos[i] > maior)
maior = voos[i];
for (i = 1; i < = n; ++i)
if (voos[i] == maior)
printf("%d ", i);
printf("\n\n");
memset(voos, 0, sizeof(voos));
}
}
Input
1 3
2 1
3 2
3 4
4 5
3 5
2 5
3 5
1 3
1 2
3 2
1 2
2 1
0 0
Output
3
Teste 2
1 2
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <:algorithm>:
#include <:cstdio>:
#include <:vector>:
#define MP make_pair
#define PB push_back
using namespace std;
typedef pair < int, int> ii;
typedef vector<int> vi;
int main() {
int n, v, teste = 1;
while (scanf("%d %d", &n, &v) && (n || v)) {
printf("Teste %d\n", teste++);
vi vetor;
for (int i = 0; i < = n; i++) vetor.PB(0);
while (v--) {
int x, y;
scanf("%d %d", &x, &y);
vetor[x]++;
vetor[y]++;
}
int grau = *(max_element(vetor.begin(), vetor.end()));
for (int i = 1; i < = n; i++) {
if (vetor[i] != grau) continue;
printf("%d ", i);
}
printf("\n\n");
}
return 0;
}
Input
1 3
2 1
3 2
3 4
4 5
3 5
2 5
3 5
1 3
1 2
3 2
1 2
2 1
0 0
Output
3
Teste 2
1 2