Задача Реконструкција

http://mendo.mk/Task.do?id=631
Идеја ? Вајда треба со graphs , или .. ? Поточно тешко ми е да го средам кога оној дел во задачата кога вели ...
„ Уште повеќе, не ни внимавала кој е од лево, а кој е од десно.“

Perez wrote:Идеја ? Вајда треба со graphs , или .. ? Поточно тешко ми е да го средам кога оној дел во задачата кога вели ...
„ Уште повеќе, не ни внимавала кој е од лево, а кој е од десно.“

Ако ја решаваш како граф, тоа лево-десно може да го средиш така што ќе го гледаш графот како да е ненасочен (неориентиран).
Нешто вака:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int k;
vector<int> G[100001];

int vis[100001];
int conn[100001];

int bfs(int from, bool backwards)
{
	int last;
	queue<int> q;

vis[from] = 1;
	q.push(from);

while (!q.empty())
	{
		last = q.front();
		q.pop();

for (int o : G[last])
		{
			if (vis[o] == 0)
			{
				q.push(o);
				vis[o] = true;
				
				if (!backwards)
				{
					conn[last] = o;
				}
				else 
				{
					conn[o] = last;
				}
			}
		}
	}

return last;
}

int main()
{
	cin >> k;
	for (int i=0; i<k-1; i++)
	{
		int f, t;
		cin >> f >> t;
		G[f].push_back(t);
		G[t].push_back(f);
	}

memset(conn, -1, sizeof(conn));
	memset(vis, 0, sizeof(vis));

int last1 = bfs(0, false);
	int last2 = bfs(k, true);

if (conn[last1] == -1)
	{
		//potrebno e da gi povrzeme posledniot element viden koga trgnavme od 0
		//i posledniot element viden koga trgnavme od k
		conn[last1] = last2;
	}
	
	int pos = 0;
	while (pos != k)
	{
		cout << pos << " ";
		pos = conn[pos];			
	}

cout << pos << endl; //pos = k (posledniot element)
	return 0;
}

А друг начин освен со граф ?

Perez wrote:А друг начин освен со граф ?

Те интересира некој конкретен пристап или...?
Ако е прашањето само "дали може да се избегне bfs, dfs, итн", може - со правилно чување на податоците при читањето. Треба само да видиш дека за една позиција, постојат најмногу два други елемента кои се поврзани со неа (лево и десно). Ако ги чуваш тие две бројки за секој елемент (на пример, нека бидат 5 и 9 - иако во моментот на читањето не знаеш кој доаѓа лево а кој десно), тогаш имајќи во предвид дека тргнувајќи од 0 секогаш ќе знаеш кој е претходниот елемент, знаеш точно кој од двата да ги искористиш. На пример, Ако си стигнал од 0 до 5 до 3, и сега лево и десно од 3 ти се 5 и 9, знаеш дека треба да одиш на 9, бидејќи 5 ти дошол претходно.

(Ме мрзеше да пишувам голем број коментари во мојот код, едвај се натерав да решавам, ама мислам дека ќе го разбереш)

#include <iostream>
#include <cstring>
using namespace std;
 
int k;
int to[100001][2];
int cnt[100001];
 
int main()
{
    cin >> k;
    memset(to, -1, sizeof(to));
    memset(cnt, 0, sizeof(cnt));
 
    for (int i=0; i<k-1; i++)
    {
        int f, m;
        cin >> f >> m;
 
        if (to[f][0] == -1) {
            to[f][0] = m;
        } else {
            to[f][1] = m;
        }
 
        if (to[m][0] == -1) {
            to[m][0] = f;
        } else {
            to[m][1] = f;
        }
 
        cnt[f]++;
        cnt[m]++;
    }
 
    int current = 0;
    int previous = -1;
 
    while (current != k) {
        cout << current << " ";
 
        if (to[current][0] != -1 && to[current][0] != previous){
            previous = current;
            current = to[current][0];
            continue;
        }
 
        if (to[current][1] != -1 && to[current][1] != previous){
            previous = current;
            current = to[current][1];
            continue;
        }
 
        //inaku, nemame sledno, pa najdi drug element koj se spomenuva pomalku od dvapati
        for (int r=1; r<=k; r++){
            if (current != r && previous != r && cnt[r] < 2){
                previous = current;
                current = r;
                break;
            }
        }
 
    }
 
    cout << k << endl;
    return 0;
}

Нема врска океј е воа фала многу ќе ги разгледам кодовите