Родословная

@dmitrii2000 · Регистрация: 03.05.2020

Студворк — интернет-сервис помощи студентам

Родословная
В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.

Каждому элементу дерева ставится в соответствие целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя.

Вам дано генеалогическое древо, определите высоту всех его элементов.

Входные данные

Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающая родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имяпотомка имяродителя.

Выходные данные

Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.

Примечание

Эта задача имеет решение сложности O(n), но вам достаточно написать решение сложности O(n2) (не считая сложности обращения к элементам словаря или ассоциативного массива).

Пример ниже соответствует приведённому древу рода Романовых.

Примеры
Ввод
9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I
Вывод
Alexander_I 4
Alexei 1
Anna 1
Elizabeth 1
Nicholaus_I 4
Paul_I 3
Peter_I 0
Peter_II 2
Peter_III 2

@dmitrii2000 · 16.08.2021, 08:04 **[ТС]**

Актуально

@YUEN HOIFEF · 17.08.2021, 11:29

C++
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
#include<stdlib.h> // atoi, itoa
#include<string.h> // strlen, strcpy, strcat ...
 
#include<iostream>
#include<fstream>
#include<vector>
 
#define MAXIMAMBNAME 50
#define MAXIBUFF     1024
 
using namespace std;
 
 
char **names = NULL;
int fmN = 0; // family mambers amount;
int nN = 0;
 
 
class FAMILY_TREE
 {
public:
 char name[ MAXIMAMBNAME ];
 vector<FAMILY_TREE>childs;
 };
 
 
void sortirovka( char **arrray )
 {
char *tmp;
for( int i=0; i<nN; i++ )
 {
 for( int j=i; j<nN; j++ )
  {
  if( stricmp(arrray[ i ], arrray[ j ]) > 0 )
   {
   tmp = arrray[ i ];
   arrray[ i ] = arrray[ j ];
   arrray[ j ] = tmp;
   }
  }
 }
return;
 }
 
 
void add_to_names_array( char *mamber_name )
 {
int flag = 0;
 
for( int i=0; i<nN && nN<fmN; i++ )
 {
 if( stricmp(names[ i ], mamber_name)==0 )
  {
  flag = 1;
  break;
  }
 }
 
if( !flag )
 {
 strncpy( names[ nN++ ], mamber_name, MAXIMAMBNAME  );
 }
return;
 }
 
 
 
 
FAMILY_TREE *find_mamber( FAMILY_TREE *mamber,  char *mamber_name, int N, int &hi )
 {
FAMILY_TREE *flag = NULL;
 
if( mamber )
 {
 for( int i=0; i<N; i++ )
  {
  if( stricmp(mamber[ i ].name, mamber_name)==0 )
   {
   flag = &mamber[ i ];
   break;
   }
  }
 
 if( !flag )
  {
  if( mamber->childs.data() )
   {
   for( int i=0; i<N;  i++ )
    {
    if( mamber[ i ].childs.data() )
     {
    int xx = mamber[ i ].childs.size();
    if( xx )
     {
     flag = find_mamber( mamber[ i ].childs.data(), mamber_name, xx, ++hi );
 
     if( flag ) break;
     --hi;
     }
     }
    }
   }
  }
 }
return flag;
 }
 
 
 
 
bool add_new_mamber( vector<FAMILY_TREE> *mambers, char *mambers_str )
 {
// - - - - - ---  - -- - - - - - 
// Get names
int j = 0, c = 0;
char parent_name[ MAXIMAMBNAME ];
char child_name[ MAXIMAMBNAME ];
 
for( int i=0, f=0; i<strlen(mambers_str); i++ )
 {
 if( mambers_str[ i ] != ' ' )
  {
  if( !f )
   {
   child_name[ j++ ] = mambers_str[ i ];
   }
  else parent_name[ c++ ] = mambers_str[ i ];
  }
 else
  {
  f = 1;
  }
 }
parent_name[ c ] = '\0';
child_name[ j ] = '\0';
 
if( !nN ) add_to_names_array( parent_name );
add_to_names_array( child_name );
// - - - - - ---  - -- - - - - -
 
 
FAMILY_TREE *mamb_ptr = mambers->data();
FAMILY_TREE tmp_mamb = { 0 };
 
mamb_ptr = find_mamber( mamb_ptr, parent_name, mambers->size(), c );
 
if( !mamb_ptr )
 {
 strncpy( tmp_mamb.name, parent_name, MAXIMAMBNAME );
 mambers->push_back( tmp_mamb );
 
 add_new_mamber( mambers, mambers_str );
 }
 
else
 {
 strncpy( tmp_mamb.name, child_name, MAXIMAMBNAME );
 mamb_ptr->childs.push_back( tmp_mamb );
 }
return true;
 }
 
 
int main()
 {
vector<FAMILY_TREE> mambers;
FAMILY_TREE *mamber_ptr;
 
char buffer[ MAXIBUFF ];
char tmp[ 20 ];
 
ifstream inpf( "family_tree.txt" ); 
 
if( !inpf )
 {
 cout << "NO File  family_tree.txt\n";
 return 1;
 }
 
 
int flag = 1;
for( int c=0, i=0; inpf.getline(buffer, sizeof(buffer)); c++, i++ )
 {
 if( !c )
  {
  fmN = atoi( buffer );
  if( !fmN )
   {
   cout << "Error in configuration file\n";
   flag = 0;
   }
  else
   {
   names = new char *[ fmN ];
   for( int j=0; j<fmN; j++ )
    {
    names[ j ] = new char[ MAXIMAMBNAME ];
    names[ j ][ 0 ] = '\0';
    }
   }
  }
 else
  {
  add_new_mamber( &mambers, buffer );
  }
 
 if( !flag ) break;
 }
 
if( strlen(names[ 0 ]) )
 {
 sortirovka( names );
 
 mamber_ptr = mambers.data();
 
 int xx = 0;
 for( int j=0; j<fmN; j++ )
  {
  xx = 0;
  find_mamber( mamber_ptr, names[ j ], mambers.size(), xx );
  cout << names[ j ] << "  " << xx << endl;
  }
 }
 
 
if( fmN )
 {
 for( int j=0; j<fmN; j++ )
  {
  delete names[ j ];
  }
 delete names;
 }
 
return 0;
 }

@RahatLukum · 17.08.2021, 11:35

Сообщение от dmitrii2000

Anna Peter_I

государыню Анна Иоановна звали, откуда Peter_I взялся?

@YUEN HOIFEF · 17.08.2021, 11:56

RahatLukum,
Товарищам фантазерам виднее. А наше дело маленькое.

@dmitrii2000 · 17.08.2021, 13:47 **[ТС]**

Сайт пишет, что программа слишком длинная

@YUEN HOIFEF · 17.08.2021, 14:06

Да ну его... .

Nishen · 17.08.2021, 14:16

Ну а к такому твой сайт готов??!! https://stackoverflow.com/ques... e-software

Добавлено через 42 секунды
А уж в родословной царской тако было сплошь и рядом) Никакого дерева у них там и подавно не было)

@YUEN HOIFEF · 18.08.2021, 08:09

C++
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
112
113
114
115
#include<stdlib.h> // atoi, itoa
#include<string.h> // strlen, strcpy, strcat ...
 
#include<iostream>
#include<fstream>
#include<vector>
 
#include<algorithm>
 
#define MAXIMAMBNAME 50
#define MAXIBUFF     1024
 
using namespace std;
 
class FAMILY_TREE
 {
public:
 char parent[ MAXIMAMBNAME ];
 char child[ MAXIMAMBNAME ];
 };
 
 
bool analyse_input( char *bu, char **ne )
 {
ne[ 0 ] = ne[ 1 ] = 0;
for( ; *bu==' '; ++bu );
ne[ 0 ] = &bu[ 0 ];
int c = 0;
for( int i=0; *bu; ++bu, i++ )
 {
 if( *bu==' ' )
  {
  c = i;
  for( ; *bu==' '; ++bu );
  ne[ 1 ] = &bu[ 0 ];
  break;
  }
 if( i==MAXIBUFF ) break;
 }
if( c ) ne[ 0 ][ c ] = '\0';
return( ne[ 0 ] && ne[ 1 ] ) ? true : false;
 }
 
 
void make_new_mamber( vector<FAMILY_TREE> *mamb, char **mamb_names, int x )
 {
FAMILY_TREE tmp_mamb = { 0 };
strncpy( tmp_mamb.parent, mamb_names[ 1 ], MAXIMAMBNAME );
strncpy( tmp_mamb.child, (( !x ) ? mamb_names[ 1 ] : mamb_names[ 0 ]), MAXIMAMBNAME );
mamb->push_back( tmp_mamb );
return;
 }
 
 
int get_deep( vector<FAMILY_TREE> *mamb, int index, int &n )
 {
FAMILY_TREE *mamb_ptr = mamb->data();
 
for( int i=mamb->size()-1; i>=0; i-- )
 {
 if( i!=index && stricmp(mamb_ptr[ i ].child, mamb_ptr[ index ].parent)==0 )
  {
  if( n > mamb->size() ) break;
  get_deep( mamb, i, ++n );
  }
 }
return n;
 }
 
 
bool fun( FAMILY_TREE a, FAMILY_TREE b )
 {
return( stricmp(b.child, a.child)>0 ) ? true : false;
 }
 
 
int main()
 {
vector<FAMILY_TREE> mambers;
FAMILY_TREE *mamber_ptr;
 
char buffer[ MAXIBUFF ];
char tmp[ 20 ];
 
ifstream inpf( "family_tree.txt" ); 
 
if( !inpf )
 {
 cout << "NO File  family_tree.txt\n";
 return 1;
 }
 
int flag = 1;
char *pchn[ 2 ];
for( int c=0; inpf.getline(buffer, sizeof(buffer));  )
 {
 if( analyse_input(buffer, pchn) )
  {
  if( !c )  make_new_mamber( &mambers, pchn, c++ );
  make_new_mamber( &mambers, pchn, c );
  }
 if( !flag ) break;
 }
 
std::sort( mambers.begin(), mambers.end(), fun );
 
for( int i=0, n=0; i<mambers.size(); i++ )
 {
 n = 0;
 get_deep( &mambers, i, n );
 cout <<  mambers[ i ].child << " " << n << endl;
 }
 
return 0;
 }

@dmitrii2000 · 18.08.2021, 08:25 **[ТС]**

Программа не компилируется

@YUEN HOIFEF · 18.08.2021, 09:32

Как два пальца об....ть.

C++
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<stdlib.h> // atoi, itoa
#include<string.h> // strlen, strcpy, strcat ...
 
#include<iostream>
#include<fstream>
 
 
 
 
#define MAXIMAMBNAME 50
#define MAXIBUFF     1024
 
using namespace std;
 
class FAMILY_TREE
 {
public:
 char parent[ MAXIMAMBNAME ];
 char child[ MAXIMAMBNAME ];
 };
 
int superTREE = 0;
 
 
void sortirovka( FAMILY_TREE *arrray )
 {
FAMILY_TREE tmp;
for( int i=0; i<superTREE; i++ )
 {
 for( int j=i; j<superTREE; j++ )
  {
  if( stricmp(arrray[ i ].child, arrray[ j ].child) > 0 )
   {
   tmp = arrray[ i ];
   arrray[ i ] = arrray[ j ];
   arrray[ j ] = tmp;
   }
  }
 }
return;
 }
 
bool analyse_input( char *bu, char **ne )
 {
ne[ 0 ] = ne[ 1 ] = 0;
for( ; *bu==' '; ++bu );
ne[ 0 ] = &bu[ 0 ];
int c = 0;
for( int i=0; *bu; ++bu, i++ )
 {
 if( *bu==' ' )
  {
  c = i;
  for( ; *bu==' '; ++bu );
  ne[ 1 ] = &bu[ 0 ];
  break;
  }
 if( i==MAXIBUFF ) break;
 }
if( c ) ne[ 0 ][ c ] = '\0';
return( ne[ 0 ] && ne[ 1 ] ) ? true : false;
 }
 
 
void make_new_mamber( FAMILY_TREE *mamb, char **mamb_names, int x )
 {
strncpy( mamb[ x ].parent, mamb_names[ 1 ], MAXIMAMBNAME );
strncpy( mamb[ x ].child, (( !x ) ? mamb_names[ 1 ] : mamb_names[ 0 ]), MAXIMAMBNAME );
return;
 }
 
 
int get_deep( FAMILY_TREE *mamb, int index, int &n )
 {
for( int i=superTREE-1; i>=0; i-- )
 {
 if( i!=index && stricmp(mamb[ i ].child, mamb[ index ].parent)==0 )
  {
  if( n > superTREE ) break;
  get_deep( mamb, i, ++n );
  }
 }
return n;
 }
 
 
 
 
int main()
 {
FAMILY_TREE *mamberss = NULL;
 
char buffer[ MAXIBUFF ];
char tmp[ 20 ];
 
ifstream inpf( "family_tree.txt" ); 
 
if( !inpf )
 {
 cout << "NO File  family_tree.txt\n";
 return 1;
 }
 
 
 
int flag = 1;
char *pchn[ 2 ];
for( int c=-1; inpf.getline(buffer, sizeof(buffer));   )
 {
 if( c==-1 )
  {
  superTREE = atoi( buffer );
  if( !superTREE ) break;
  mamberss = new FAMILY_TREE[ superTREE ];
  ++c;
  }
 else if( analyse_input(buffer, pchn) )
  {
  if( !c )  make_new_mamber( mamberss, pchn, c++ );
  make_new_mamber( mamberss, pchn, c );
  ++c;
  }
 if( !flag ) break;
 }
 
 
if( superTREE )
 {
 sortirovka( mamberss );
 for( int i=0, n=0; i<superTREE; i++ )
  {
  n = 0;
  get_deep( mamberss, i, n );
  cout <<  mamberss[ i ].child << " " << n << endl;
  }
 
 delete mamberss;
 }
 
return 0;
 }

Проверено на двух компиляторах.

@RahatLukum · 18.08.2021, 10:54

C++
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
int find(string n,vector<string> v)
{
    for(int i=0; i<(int)v.size(); i++)
        if(v[i]==n) return i;
    return -1;
}
int main()
{
    //string p[]={"Peter_I","Peter_I","Peter_I","Alexei","Anna","Peter_III","Paul_I","Paul_I"};
    //string c[]={"Alexei","Anna","Elizabeth","Peter_II","Peter_III","Paul_I","Alexander_I","Nicholaus_I"};
    int n=9;
    cin>>n;
    vector<string> pr(n-1);
    vector<string> ch(n-1);
    pair<string,int> m;
    vector<pair<string,int>> v;
    for(int i=0; i<n-1; i++)
    {
        cin>>ch[i]>>pr[i];
        //ch[i]=c[i];
        //pr[i]=p[i];
    }
    for(int k,i=0; i<(int)ch.size(); i++)
    {
        m.first=ch[i];
        m.second=1;
        for(string p=pr[i]; (k=find(p,ch))>=0; p=pr[k])
            m.second++;
        v.push_back(m);
    }
    for(int k,i=0; i<(int)pr.size(); i++)
        if(find(pr[i],ch)<0)
        {
            m.first=pr[i];
            m.second=0;
            v.push_back(m);
            while((k=find(m.first,pr))>=0)
                pr.erase(pr.begin()+k);
            i--;
        }
    sort(v.begin(),v.end());
    for(int i=0; i<(int)v.size(); i++)
        cout<<v[i].first<<" "<<v[i].second<<endl;
    system("pause");
    return 0;
}

@Leranest · 20.08.2022, 14:39

актуально!

Ни один из кодов, приведенных выше, тестирующая система Сириуса не принимает. Я пытаюсь написать свой, но самое главное - как сопоставить каждому человеку его уровень - не получается вообще, я просто не понимаю, как это делать..

Мой код:

C++
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
#include <iostream>
#include <set>
#include <map>
 
using namespace std;
typedef long long ll;
 
int main()
{
    ll n;
    cin >> n;
    set <string> parents;
    set <string> children;
    set <string> all;
    map <string, string> m1;
    map <string, int> ans;
    for (ll i = 0; i < n - 1; ++i) {
        string child, parent;
        cin >> child >> parent;
        m1[child] = parent;
        parents.insert(parent);
        children.insert(child);
        all.insert(parent);
        all.insert(child);
    }
 
    string zero;
    for (auto c : parents) {
        if (children.find(c) == children.end()) {
            zero = c;
            break;
        }
    }
    ans[zero] = 0;
    
    //ЗДЕСЬ ДОЛЖЕН БЫТЬ КОД, СОПОСТАВЛЯЮЩИЙ КАЖДОМУ ЧЕЛОВЕКУ ЕГО УРОВЕНЬ.
    
    return 0;
}

@domiitori · 26.08.2022, 23:26

актуально?

я дополнил код выше, реализовав подсчет уровня рекурсивным методом
Сириус принял решение

P.S. до закрытия блока осталось пол часа

C++
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
#include <iostream>
#include <set>
#include <map>
 
using namespace std;
typedef long long ll;
 
set <string> parents;
set <string> children;
set <string> all;
map <string, string> m1;
map <string, set<string>> m2;
map <string, int> ans;
 
int myDef(string man, int i)
{
    if (parents.find(man) != parents.end())
        for (auto child : m2[man])
            ans[child] = myDef(child, i + 1);
    
    return i;
}
 
int main()
{
    ll n;
    cin >> n;
    for (ll i = 0; i < n - 1; ++i) {
        string child, parent;
        cin >> child >> parent;
        m1[child] = parent;
        m2[parent].insert(child);
        parents.insert(parent);
        children.insert(child);
        all.insert(parent);
        all.insert(child);
    }
 
    string zero;
    for (auto c : parents) {
        if (children.find(c) == children.end()) {
            zero = c;
            break;
        }
    }
    ans[zero] = 0;
 
    myDef(zero, 0);
 
    for (auto a : ans)
        cout << a.first << " " << a.second << endl;
 
    return 0;
}

Добавлено через 2 минуты
привел решение

@Leranest · 27.08.2022, 12:33

Эх... Не успела... Ну ничего, спасибо

@DeNaOl · 19.08.2025, 18:14

Сейчас решил эту задачу
Решается бфсом за O(V + E) если не ошибаюсь

C++
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
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <unordered_set>
 
using namespace std;
 
void bfs(int x, vector<vector<int>>& G, vector<int>& dist) {
    queue<int> q;
 
    q.push(x);
    dist[x] = 0;
 
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : G[v]) {
            if (dist[u] == -1) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
}
 
int find_root(int v, vector<vector<int>>& G_rev) {
    while (!G_rev[v].empty()) {
        v = G_rev[v][0];
    }
    return v;
}
 
int main() {
    int n;
    cin >> n;
    vector<string> dict(n + 1);
    map<string, int> dict_r;
    unordered_set<string> us;
    int cnt = 1;
    vector<vector<int>> G(n + 1);
    vector<vector<int>> G_rev(n + 1);
    bool flag;
 
 
 
    for (int i = 0; i < n - 1; ++i) {
        string v, u;
        cin >> v >> u;
 
        if (find(us.begin(), us.end(), u) == us.end()) {
            dict[cnt] = u;
            dict_r[u] = cnt;
;           us.insert(u);
            ++cnt;
        }
 
        if (find(us.begin(), us.end(), v) == us.end()) {
            dict[cnt] = v;
            dict_r[v] = cnt;
            us.insert(v);
            ++cnt;
        }
 
        G[dict_r[u]].push_back(dict_r[v]);
        G_rev[dict_r[v]].push_back(dict_r[u]);
    }
 
    vector<int> dist(n + 1, -1);
    int start = find_root(1, G_rev);
    bfs(start, G, dist);
    vector<pair<string, int>> ans;
    for (int i = 1; i < G.size(); ++i) {
        ans.push_back({ dict[i], dist[i] });
    }
    sort(ans.begin(), ans.end());
    for (auto i : ans) {
        cout << i.first << ' ' << i.second << '\n';
    }
}

зарегался только ради того, чтобы показать это решение

@SmallEvil · 20.08.2025, 14:19

Сообщение от DeNaOl

Решается бфсом

Графы рулят.
bfs без каких либо преобразований, вершины это строки/имена.
И без поиска корня/первородного.
Добавил имен и std::get хоть для какой то наглядности.

C++
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
#include <iostream>
#include <map>
#include <string>
#include <queue>
#include <forward_list>
#include <unordered_set>
#include <utility>
int main(){
   using std::string;
   using std::pair;
   using std::get;
   int n; std::cin >> n;
   
   // <name, parent_link>, relative_height>
   std::map<string, pair<std::forward_list<pair<string, bool>>, int>> dict;
   std::unordered_set<string> visited;
   std::string child, parent;
 
   for(int i = 1; i != n; ++i){
      std::cin >> child >> parent;
      dict[child].first.emplace_front(parent, true);
      dict[parent].first.emplace_front(child, false);
   }
   
   std::queue<pair<string, int>> q;
   if (n > 1){
      q.emplace(dict.begin()->first, 0);
      visited.insert(dict.begin()->first);
   }
   
   const int Name = 0;
   const int Data = 1;
   const int Height = 1; 
   const int Link = 0;
   const int Parent = 1;
   int min = 0;
   while(!q.empty()){
      for(int i = 0, end = q.size(); i != end; ++i){
         auto v = q.front(); q.pop();
         min = std::min(get<Height>(v), min);
         for(auto link : get<Link>(dict[get<Name>(v)]))
            if (auto [it, success] = visited.insert(get<Name>(link)); success){
               int height = get<Parent>(link) ? get<Height>(v) - 1 : get<Height>(v) + 1;
               q.emplace(get<Name>(link), height);
               get<Height>(dict[get<Name>(link)]) = height;
            }
      }
   }
   int d = -min;
   for(auto& [name, data] : dict)
      std::cout << name << ' ' << (get<Height>(data) + d) << '\n';
   std::cout << std::endl; // flush
}

Дело было вечером, делать было нечего)

@Royal_X · 28.08.2025, 12:45

Не по теме:

Увидев 4-й пост, сперва подумал, что на форум вернулся легендарный фрилансер-мошенник RahatLukum, он же Exp2dot7 (настоящее имя Тимур Мансурович). А оказалось, что просто восстановили некропост.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202

	Родословная 15.08.2021, 05:03. Показов 12492. Ответов 17 Метки нет (Все метки) Родословная В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель. Каждому элементу дерева ставится в соответствие целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя. Вам дано генеалогическое древо, определите высоту всех его элементов. Входные данные Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающая родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имяпотомка имяродителя. Выходные данные Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту. Примечание Эта задача имеет решение сложности O(n), но вам достаточно написать решение сложности O(n2) (не считая сложности обращения к элементам словаря или ассоциативного массива). Пример ниже соответствует приведённому древу рода Романовых. Примеры Ввод 9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I Вывод Alexander_I 4 Alexei 1 Anna 1 Elizabeth 1 Nicholaus_I 4 Paul_I 3 Peter_I 0 Peter_II 2 Peter_III 2 0

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202
	16.08.2021, 08:04 [ТС]
	Актуально 0

@YUEN HOIFEF 252 / 185 / 47 Регистрация: 31.01.2021 Сообщений: 934
	17.08.2021, 11:56
	RahatLukum, Товарищам фантазерам виднее. А наше дело маленькое. 0

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202
	17.08.2021, 13:47 [ТС]
	Сайт пишет, что программа слишком длинная 0

@YUEN HOIFEF 252 / 185 / 47 Регистрация: 31.01.2021 Сообщений: 934
	17.08.2021, 14:06
	Да ну его... . 2

Nishen 1358 / 856 / 366 Регистрация: 26.02.2015 Сообщений: 3,814
	17.08.2021, 14:16
	Ну а к такому твой сайт готов??!! https://stackoverflow.com/ques... e-software Добавлено через 42 секунды А уж в родословной царской тако было сплошь и рядом) Никакого дерева у них там и подавно не было) 1

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202
	18.08.2021, 08:25 [ТС]
	Программа не компилируется 0

@Leranest 5 / 5 / 0 Регистрация: 08.05.2020 Сообщений: 33
	27.08.2022, 12:33
	Эх... Не успела... Ну ничего, спасибо 0

@Royal_X
	28.08.2025, 12:45
	Не по теме: Увидев 4-й пост, сперва подумал, что на форум вернулся легендарный фрилансер-мошенник RahatLukum, он же Exp2dot7 (настоящее имя Тимур Мансурович). А оказалось, что просто восстановили некропост. 0