5220 2023. 04. 22 22:24:15 Valaki2 Turista járatok cpp14 Hibás válasz 40/100 140ms 72428 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

struct edge {
    int from, to, id;
};

const int maxn = 40'000;
const int maxm = 400'000;
const int root = 1;
const int maxc = maxm; // actually maxn should be enough!!!!!

int n, m, k;
vector<edge> graph[1 + maxn];
pii edges[1 + maxm];

/*bool special(const edge &e) {
    return e.id <= k;
}*/

int t;
int dep[1 + maxn];
int low[1 + maxn];
bool cut[1 + maxn];

stack<int> s;
int comp_cnt;
int start[1 + maxc];
int comp[1 + maxm];
int nodes_comp[1 + maxn];

bool vis_low[1 + maxn];

void dfs_low(int cur, int par) {
    t++;
    dep[cur] = t;
    low[cur] = t;
    vis_low[cur] = true;
    int cnt = 0;
    for(const edge &e : graph[cur]) {
        int nei = e.to;
        if(!vis_low[nei]) {
            cnt++;
            s.push(e.id);
            dfs_low(nei, cur);
            low[cur] = min(low[cur], low[nei]);
            if((par == -1) || (par != -1 && low[nei] >= dep[cur])) {
                comp_cnt++;
                start[comp_cnt] = cur;
                while(!s.empty()) {
                    comp[s.top()] = comp_cnt;
                    if(s.top() == e.id) {
                        s.pop();
                        break;
                    } else {
                        s.pop();
                    }
                }
            }
        } else if(nei != par) {
            if(dep[nei] <= low[cur]) {
                low[cur] = dep[nei];
                s.push(e.id);
            }
        }
    }
}

//bool vis_bcc[1 + maxn];

/*void dfs_bcc(int cur, int prv_id) {
    vis_bcc[cur] = true;
    for(const edge &e : graph[cur]) {
        if(!vis_bcc[e.to]) {
            s.push(e.id);
            dfs_bcc(e.to, e.id);
            if((low[e.to] >= dep[cur]) && (cut[cur] || cur == root)) {
                comp_cnt++;
                start[comp_cnt] = cur;
                while(!s.empty() && s.top() != e.id) {
                    comp[s.top()] = comp_cnt;
                    s.pop();
                }
                if(!s.empty()) {
                    comp[s.top()] = comp_cnt;
                    s.pop();
                }
            }
        } else if(e.id != prv_id && dep[e.to] < low[cur]) {
            s.push(e.id);
        }
    }
}*/

vector<int> tree[1 + maxc];
bool has[1 + maxc];

void dfs_has(int cur, bool have) {
    if(have) {
        has[cur] = true;
    }
    have = has[cur];
    for(int nei : tree[cur]) {
        dfs_has(nei, have);
    }
}

void solve() {
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].pb({a, b, i});
        graph[b].pb({b, a, i});
        edges[i] = mp(a, b);
    }
    dfs_low(root, -1);
    //dfs_bcc(root, -1);
    for(int i = 1; i <= m; i++) {
        if(comp[i] != 0) {
            if(start[comp[i]] != edges[i].fi) {
                nodes_comp[edges[i].fi] = comp[i];
            }
            if(start[comp[i]] != edges[i].se) {
                nodes_comp[edges[i].se] = comp[i];
            }
        }
    }
    for(int i = 1; i <= comp_cnt; i++) {
        tree[nodes_comp[start[i]]].pb(i);
    }
    for(int i = 1; i <= k; i++) {
        has[comp[i]] = true;
    }
    dfs_has(0, false);
    vector<int> ans;
    for(int i = 1; i <= n; i++) {
        if(has[nodes_comp[i]]) {
            ans.pb(i);
        }
    }
    cout << ans.size() << "\n";
    for(int x : ans) {
        cout << x << " ";
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 10ms 22580 KiB
2 Hibás válasz 17ms 25096 KiB
subtask2 10/10
3 Elfogadva 12ms 23028 KiB
4 Elfogadva 9ms 23112 KiB
5 Elfogadva 10ms 23244 KiB
6 Elfogadva 9ms 23372 KiB
7 Elfogadva 12ms 23732 KiB
subtask3 10/10
8 Elfogadva 10ms 23800 KiB
9 Elfogadva 9ms 24004 KiB
10 Elfogadva 9ms 24244 KiB
11 Elfogadva 13ms 24636 KiB
12 Elfogadva 14ms 25536 KiB
subtask4 10/10
13 Elfogadva 17ms 26576 KiB
14 Elfogadva 13ms 24884 KiB
15 Elfogadva 10ms 25104 KiB
16 Elfogadva 12ms 25472 KiB
17 Elfogadva 140ms 72424 KiB
18 Elfogadva 50ms 35028 KiB
19 Elfogadva 64ms 38832 KiB
20 Elfogadva 57ms 35128 KiB
subtask5 10/10
21 Elfogadva 18ms 26856 KiB
22 Elfogadva 10ms 25168 KiB
23 Elfogadva 10ms 25176 KiB
24 Elfogadva 10ms 25188 KiB
25 Elfogadva 96ms 55288 KiB
26 Elfogadva 17ms 26948 KiB
27 Elfogadva 16ms 26944 KiB
subtask6 0/60
28 Elfogadva 13ms 25228 KiB
29 Hibás válasz 10ms 25364 KiB
30 Hibás válasz 12ms 25584 KiB
31 Hibás válasz 12ms 25808 KiB
32 Elfogadva 13ms 25852 KiB
33 Hibás válasz 14ms 26148 KiB
34 Hibás válasz 17ms 27172 KiB
35 Hibás válasz 17ms 27164 KiB
36 Hibás válasz 19ms 27172 KiB
37 Elfogadva 138ms 72428 KiB
38 Elfogadva 48ms 35224 KiB
39 Elfogadva 54ms 35468 KiB
40 Elfogadva 50ms 35536 KiB
41 Elfogadva 50ms 35604 KiB
42 Elfogadva 52ms 35512 KiB
43 Elfogadva 52ms 35496 KiB
44 Elfogadva 52ms 35376 KiB
45 Elfogadva 68ms 39412 KiB
46 Elfogadva 52ms 35636 KiB
47 Elfogadva 52ms 35804 KiB
48 Elfogadva 52ms 35644 KiB
49 Elfogadva 54ms 35856 KiB
50 Elfogadva 54ms 35788 KiB