Description
UVa 10928 - My Dear Neighbours
Problem: Find the minimum number of neighbours.
Sample Input
The first line of the input is N ≤ 30 that indicates the number of test cases. Each test case consists of a number P, where 2 ≤ P ≤ 1000, that indicates the number of places where Manuel can live, each place is numbered from 1 to P. Then there will be P lines indicating the neighbours of each place, each neighbour is separated by exactly one space. Each place has at least 1 neighbour and at most P − 1 neighbours, because Manuel can not be a neighbour of himself. For this problem if P1 has P2 as his neighbour does not mean that P2 has P1 as his neighbour. Each test case is separated by a blank line
1
2
3
4
5
6
7
8
9
10
11
12
2
3
2
1 3
2 1
4
2
3
1 4 2
2 1 3
Sample Output
For each test case you should print the place that has the minimum number of neighbours. If there are more than one you should print all places separeted by one space and ordered by the indices, the lower indices should come first.
1
2
3
1
1 2
Ideas
Sort the vertices according to ther cardinality and print all the vertices with minimum cardinality.
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/******************** Beginning of Template **************************/
/************ ALL HEADER FILE ***********/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <utility>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <cassert>
/************************************ ALL DEFINE ****************************************************/
#define FORS(i, j, k, step) for (int i = j; i < k; i += step)
#define FOR(i, j, k) for (int i = j; i < k; i++)
#define RFORS(i, j, k, step) for (int i = j; i >= k; i -= step)
#define RFOR(i, j, k, step) for (int i = j; i >= k; i--)
#define REP(i, k) for (int i = (0); i < (k); i++)
#define RREP(i, k) for (int i = j; i >= (k); i--)
#define ALL(cont) cont.begin(), cont.end()
#define RALL(cont) cont.begin(), cont.end()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define mp make_pair
#define pb push_back
#define RESET(a, b) memset(a, b, sizeof(a))
#define INF (int)INT_MAX
#define EPS (int)1e-9
#define PI acos(-1)
#define MOD 1000000007
#define MIN(A, B) A < B ? A : B
using namespace std;
/************************************ END OF DEFINE ****************************************************/
/************************************ ALL TYPEDEF ****************************************************/
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<piii> viii;
typedef long long int32;
typedef unsigned long long uint32;
typedef long long int int64;
typedef unsigned long long int uint64;
template <class T>
T sqr(T val)
{
return val * val;
}
/************************************ ALL DEFINE ****************************************************/
/************************************ END OF PREHEADER ***********************************************/
int main()
{
int t;
cin >> t;
while (t--)
{
int min_val = INF;
int n;
cin >> n;
//clear buffer
getchar();
n++;
vi graph(n, 0);
FOR(i, 1, n)
{
string s;
int x = 1;
getline(cin, s);
for (int j = 0; j < s.length(); j++)
{
if (s[j] == ' ')
x++;
}
graph[i] = x;
min_val = MIN(min_val, graph[i]);
}
vi ans;
FOR(i, 1, n)
{
if (graph[i] == min_val)
ans.push_back(i);
}
for (int i = 0; i < ans.size(); i++)
{
cout << ans[i] << (i != ans.size() - 1 ? " " : "\n");
}
}
return 0;
}