97582024-03-06 13:17:54FulopMateEmezen Rt.cpp17Hibás válasz 0/100263ms49432 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define MAX(a, b) (a) = max((a), (b))
#define MIN(a, b) (a) = min((a), (b))
#define all(a) (a).begin(), (a).end()
#define sortedpair(a, b) {min((a), (b)), max((a), (b))}

const ll MOD = 1e9+7;

const int MAXN = 100'001;

struct E {
    int u, v, w;

    E(int a, int b, int c) : u(a), v(b), w(c) {}
};

int par[MAXN], ans[MAXN];
vector<int> g[MAXN];

int get(int u) {
    if (par[u] == u) return u;
    return par[u]=get(par[u]);
}

bool unio(int u, int v) {
    u = get(u); v=get(v);
    if (u == v) return false;
    par[u]=v;
    return true;
}

void dfs(int u, int p = -1, int d = 0) {
    ans[u] = d&1;
    for (int v : g[u]) {
        if (v != p) dfs(v, u, d+1);
    }
}

void solve(){
    int n, m; cin>>n>>m;
    iota(par, par+n+1, 0);
    map<pair<int, int>, int> mp;
    vector<pair<int, int>> a;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        a.emplace_back(u, v);
        if (u > v) swap(u, v);
        mp[{u, v}]++;
    }
    for (int i = 1; i <= n; i++) {
        g[i].clear();
    }

    vector<E> edges;
    for (auto [e, x] : mp) {
        edges.emplace_back(e.first, e.second, x);
    }
    sort(edges.begin(), edges.end(), [](auto x, auto y){
        return x.w > y.w;
    });
    for (E e : edges) {
        if (unio(e.u, e.v)) {
            g[e.u].emplace_back(e.v);
            g[e.v].emplace_back(e.u);
        }
    }
    dfs(1);
    int ok = 0;
    for (auto [u, v] : a) {
        if (ans[u] == ans[v]) ok++;
    }
    if (ok > m/2) {
        cout << "-1\n";
        return;
    }
    int cnt = count(ans+1, ans+n+1, 1);
    cout << cnt << "\n";
    for (int i = 1; i <= n; i++) {
        if (ans[i]) cout << i << " ";
    }
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int _t = 1;
    cin >> _t;
    while (_t--) {
        solve();
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms6608 KiB
subtask20/16
2Hibás válasz4ms6904 KiB
3Elfogadva4ms7216 KiB
4Elfogadva4ms7508 KiB
5Elfogadva4ms7732 KiB
6Elfogadva4ms7680 KiB
7Hibás válasz4ms7512 KiB
8Hibás válasz4ms7688 KiB
9Elfogadva4ms7768 KiB
10Hibás válasz4ms7608 KiB
11Hibás válasz4ms7868 KiB
12Elfogadva4ms7960 KiB
13Elfogadva4ms8028 KiB
14Elfogadva4ms7968 KiB
15Elfogadva4ms8232 KiB
16Elfogadva4ms8284 KiB
subtask30/18
17Elfogadva79ms26684 KiB
18Elfogadva186ms45512 KiB
19Elfogadva186ms45516 KiB
20Hibás válasz8ms10292 KiB
21Elfogadva100ms31084 KiB
22Elfogadva150ms40164 KiB
23Elfogadva209ms45744 KiB
24Elfogadva246ms47376 KiB
25Elfogadva225ms48992 KiB
26Elfogadva263ms49056 KiB
subtask40/66
27Hibás válasz8ms10724 KiB
28Hibás válasz21ms14572 KiB
29Elfogadva54ms21984 KiB
30Elfogadva175ms40636 KiB
31Elfogadva232ms49212 KiB
32Elfogadva231ms49432 KiB
33Elfogadva226ms48792 KiB
34Elfogadva225ms47856 KiB
35Hibás válasz190ms46124 KiB
36Hibás válasz189ms46124 KiB
37Hibás válasz6ms9476 KiB
38Elfogadva10ms11052 KiB
39Hibás válasz24ms14332 KiB
40Elfogadva4ms9568 KiB
41Hibás válasz6ms9924 KiB
42Elfogadva57ms9216 KiB
43Hibás válasz24ms9224 KiB
44Hibás válasz7ms9248 KiB
45Hibás válasz4ms9256 KiB