Zadanie Cło 1 etap XV OI

Question

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/ptF7RsWMiiMdzzZWt5BKFAnT/site/?key=statement

Jedynie jaki miałem pomysł, to przetwarzać wierzchołki od najmniejszej liczby krawedzi, ale to raczej nie zadziała.

Z góry dziękuję za pomoc i poświęcony czas!

Answer 1

Rozrysuj sobie proste przypadki: drzewo, cykl, dwa cykle i zobacz kiedy istnieje rozwiązanie. To jest całkiem proste zadanie jak już zauważysz kiedy rozwiązanie istnieje

Comments

to co wydaje mi się, to że dla drzewa zawszsze nie da się, a jak mamy jakieś drzewo i dodamy jakąś krawędź, to zawsze się da. To jest okej i wystarczy?

---

bo jak by tak było, to mogę chyba stosunkowo łatwo odtworzyć wynik dla drzewa z przynajmniej jedną krawędzią. Idę sobie DFS-em od jakiegoś wierzchołka i szukam cyklu i jak go znajdę, to jednemu (temu co brakuje w drzewie np korzeniowi) daję tą dodatkową krawędź a reszta to symulacja DFS-em od tego wierzchołka, w tym przypadku korzenia.

---

Tak, to jest dobry pomysł

---

Przeszło na 100pkt.

Można to zaimplementować w kilku krokach.

1* - Dzielimy graf na spójne składowe

2* - Dla każdej składowej odpalamy właśnie ten algorytm, że jak jest drzewo z dodatkową krawędzią to git i odpalamy tego DFS-a/BFS-a z odtwarzaniem a jak nie to piszemy NIE.

Trzeba pamiętać, że może być wiele spójnych składowych i dla każdej odpalić ten algorytm. Mi trochę czasu zajeło debugowanie tego.

Kod dający 100pkt:

#include <iostream>
#include <vector>

using namespace std;

struct Krawedz_wejscie
{
    int a;
    int b;
    bool czy_usuwamy;
};

struct Krawedz
{
    int wierzcholek;
    int numer_krawedzi;
};

int n = 0, m = 0, a = 0, b = 0, korzen = -1, krawedz_dodatkowa = 0, ile_spojnych = 0;
vector<vector<Krawedz>> krawedzie;
vector<Krawedz_wejscie> krawedzie_wejscie;
vector<bool> czy_bylismy;
vector<int> wyn_vect;
vector<int> jaki_wierzcholek_w_spojnej;
vector<int> wyniki_korzen;
vector<int> wyniki_krawedz_dodatkowa;

void DFS(int v, int parent)
{
    czy_bylismy[v] = true;
    for (int i = 0; i < krawedzie[v].size(); ++i)
    {
        int wierz = krawedzie[v][i].wierzcholek;
        if (wierz == parent)
            continue;
        if (czy_bylismy[wierz] == true)
        {
            krawedzie_wejscie[krawedzie[v][i].numer_krawedzi].czy_usuwamy = true;
            korzen = wierz;
            krawedz_dodatkowa = krawedzie[v][i].numer_krawedzi;
        }
        else
            DFS(wierz,v);
    }
}

void DFS_odtwarzanie(int v)
{
    czy_bylismy[v] = true;
    for (int i = 0; i < krawedzie[v].size(); ++i)
    {
        int wierz = krawedzie[v][i].wierzcholek;
        if (czy_bylismy[wierz] == true)
            continue;
        if (krawedzie_wejscie[krawedzie[v][i].numer_krawedzi].czy_usuwamy == true)
            continue;
        wyn_vect[wierz] = v;
        DFS_odtwarzanie(wierz);
    }
}

void DFS_spojne(int v)
{
    czy_bylismy[v] = true;
    jaki_wierzcholek_w_spojnej[ile_spojnych] = v;
    for (int i = 0; i < krawedzie[v].size(); ++i)
    {
        int wierz = krawedzie[v][i].wierzcholek;
        if (czy_bylismy[wierz] == false)
            DFS_spojne(wierz);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    krawedzie.assign(n+1,{});
    krawedzie_wejscie.assign(m,{-1,-1,false});
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
        krawedzie_wejscie[i] = {a,b,false};
        krawedzie[a].push_back({b,i});
        krawedzie[b].push_back({a,i});
    }

    czy_bylismy.assign(n+1,false);
    for (int i = 1; i <= n; ++i)
    {
        if (czy_bylismy[i] == false)
        {
            jaki_wierzcholek_w_spojnej.push_back(-1);
            DFS_spojne(i);
            ++ile_spojnych;
        }
    }

    fill(czy_bylismy.begin(),czy_bylismy.end(),false);
    for (int i = 0; i < ile_spojnych; ++i)
    {
        korzen = -1;
        DFS(jaki_wierzcholek_w_spojnej[i],-1);
        if (korzen == -1)
        {
            cout << "NIE" << '\n';
            return 0;
        }
        wyniki_korzen.push_back(korzen);
        wyniki_krawedz_dodatkowa.push_back(krawedz_dodatkowa);
    }

    cout << "TAK" << '\n';
    fill(czy_bylismy.begin(),czy_bylismy.end(),false);
    wyn_vect.assign(n+1,-1);

    for (int i = 0; i < ile_spojnych; ++i)
    {
        korzen = wyniki_korzen[i], krawedz_dodatkowa = wyniki_krawedz_dodatkowa[i];
        if (krawedzie_wejscie[krawedz_dodatkowa].a == korzen)
            wyn_vect[korzen] = krawedzie_wejscie[krawedz_dodatkowa].b;
        else
            wyn_vect[korzen] = krawedzie_wejscie[krawedz_dodatkowa].a;
        DFS_odtwarzanie(korzen);
    }

    for (int i = 1; i <= n; ++i)
        cout << wyn_vect[i] << ' ';

    return 0;
}

Dzięki!

---

Wygląda na trochę przekombinowane :) Tu jest moje stare rozwiązanie:

#include <bits/stdc++.h>

typedef unsigned short us;
typedef short s;
typedef unsigned long ul;
typedef long l;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const l INF = 1e9 + 9;
const l MOD = 1e9 + 7;
const l PRIME = 200003;
const ll L_INF = 1e18 + 1;
const double EPS = 10e-9;

#define FOR(x, y, z) for (l z = x; z < y; z++)
#define FORE(x, y, z) for (l z = x; z <= y; z++)
#define FORD(x, y, z) for (l z = x; z > y; z--)
#define FORDE(x, y, z) for (l z = x; z >= y; z--)
#define REP(x, y) for (l y = 0; y < x; y++)

#define PF push_front
#define POF pop_front
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FS first
#define SC second

using namespace std;

l num_vertices, num_edges, end_point = -1;
l parent[100005], answer[100005];
vector<l> graph[100005];
bool visited[100005];

void dfs(l v, l p = -1)
{
	visited[v] = true;
	parent[v] = p;

	for (auto u : graph[v])
	{
		if (u != parent[v])
		{
			if (visited[u])
			{
				if (end_point == -1)
				{
					end_point = u;
					answer[u] = v;
				}
			}

			else
			{
				answer[u] = v;
				dfs(u, v);
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> num_vertices >> num_edges;

	REP(num_edges, i)
	{
		l a, b;
		cin >> a >> b;
		graph[a].PB(b);
		graph[b].PB(a);
	}

	FORE(1, num_vertices, i)
	{
		if (visited[i])
			continue;

		dfs(i);

		if (end_point == -1)
		{
			cout << "NIE\n";
			return 0;
		}

		while (end_point != i)
		{
			answer[parent[end_point]] = end_point;
			end_point = parent[end_point];
		}

		end_point = -1;
	}

	cout << "TAK\n";

	FORE(1, num_vertices, i)
	cout << answer[i] << "\n";
}

---

No trochę przekombinowane.....