221232026-01-14 17:13:52HoraEgyirányú egyensúlycpp17Elfogadva 50/5050ms6964 KiB
#include <bits/stdc++.h>
using namespace std;

vector<vector<array<int, 2>>> g; //hova, index
vector<bool> vis;
vector<int> ans, cnt;

void dfs(int v){
    while(cnt[v] < g[v].size()){
        if(!vis[g[v][cnt[v]][1]]){
            vis[g[v][cnt[v]][1]] = true;
            ans[g[v][cnt[v]][1]] = v;
            dfs(g[v][cnt[v]++][0]);
        }
        else cnt[v]++;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    g.resize(n + 2);
    vis.resize(m + 3 * n, false);
    ans.resize(m + 3 * n);
    cnt.resize(n + 2, 0);
    vector<array<int, 2>> e(m);
    for(int i = 0; i < m; i++){
        cin >> e[i][0] >> e[i][1];
        g[e[i][0]].push_back({e[i][1], i});
        g[e[i][1]].push_back({e[i][0], i});
    }
    int j = m;
    int szaml = 0;
    for(int i = 1; i <= n; i++){
        if(g[i].size() % 2 == 1){
            g[i].push_back({n + 1, j});
            g[n + 1].push_back({i, j++});
            szaml++;
        }
    }
    dfs(n + 1);
    for(int i = 1; i <= n; i++){
        if(cnt[i] != g[i].size()) dfs(i);
    }
    cout << szaml << "\n";
    for(int i = 0; i < m; i++){
        if(e[i][0] == ans[i]) cout << "-> ";
        else cout << "<- ";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/039ms5172 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva2/21ms316 KiB
9Elfogadva2/21ms316 KiB
10Elfogadva2/22ms448 KiB
11Elfogadva2/22ms564 KiB
12Elfogadva2/22ms316 KiB
13Elfogadva3/39ms1608 KiB
14Elfogadva3/321ms3512 KiB
15Elfogadva3/325ms4348 KiB
16Elfogadva3/325ms3108 KiB
17Elfogadva3/313ms2612 KiB
18Elfogadva3/326ms2616 KiB
19Elfogadva3/328ms3316 KiB
20Elfogadva3/341ms5476 KiB
21Elfogadva3/345ms5704 KiB
22Elfogadva3/350ms6964 KiB