32812023-02-23 18:57:22zsomborEgyirányú egyensúlycpp17Elfogadva 50/5046ms8828 KiB
#include <iostream>
#include <vector>
using namespace std;

int n, m, a, b;
vector <int> e1;
vector <int> e2;
vector <int> fok(2e4 + 1, 0);
vector <int> ptn;
vector <vector <int>> g(2e4 + 1);
vector <bool> volt(6e4, false);
vector <bool> dir(6e4, false);

void del(int x) {
    swap(g[x][0], g[x].back());
    g[x].pop_back();
}

void euler(int x) {
    while (g[x].size()) {
        int i = g[x][0]; del(x);
        if (volt[i]) continue;
        volt[i] = true;
        dir[i] = (e1[i] == x);
        euler((e1[i] == x ? e2[i] : e1[i]));
    }
}

int main()
{
    cin >> n >> m;
    e1.resize(m); e2.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> e1[i] >> e2[i];
        fok[e1[i]]++;
        fok[e2[i]]++;
    }
    for (int i = 1; i <= n; i++) if (fok[i] % 2) ptn.push_back(i);
    for (int i = 0; i < ptn.size(); i += 2) {
        e1.push_back(ptn[i]);
        e2.push_back(ptn[i + 1]);
    }
    for (int i = 0; i < e1.size(); i++) {
        g[e1[i]].push_back(i);
        g[e2[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) euler(i);
    cout << ptn.size() << endl;
    for (int i = 0; i < m; i++) cout << (dir[i] ? "-> " : "<- ");
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms2708 KiB
2Elfogadva0/034ms6580 KiB
3Elfogadva2/23ms3192 KiB
4Elfogadva2/23ms3404 KiB
5Elfogadva2/23ms3392 KiB
6Elfogadva2/23ms3396 KiB
7Elfogadva2/23ms3600 KiB
8Elfogadva2/23ms4160 KiB
9Elfogadva2/23ms3904 KiB
10Elfogadva2/24ms4380 KiB
11Elfogadva2/24ms4508 KiB
12Elfogadva2/24ms4556 KiB
13Elfogadva3/310ms5188 KiB
14Elfogadva3/318ms6232 KiB
15Elfogadva3/321ms7932 KiB
16Elfogadva3/325ms7536 KiB
17Elfogadva3/313ms6552 KiB
18Elfogadva3/327ms7228 KiB
19Elfogadva3/327ms6920 KiB
20Elfogadva3/337ms8344 KiB
21Elfogadva3/341ms8160 KiB
22Elfogadva3/346ms8828 KiB