5222 2023. 04. 22 22:59:54 Valaki2 Turista járatok cpp14 Elfogadva 100/100 149ms 72660 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++) {
        if(comp[i] != 0) {
            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 22548 KiB
2 Elfogadva 18ms 24740 KiB
subtask2 10/10
3 Elfogadva 9ms 22972 KiB
4 Elfogadva 12ms 23160 KiB
5 Elfogadva 12ms 23500 KiB
6 Elfogadva 9ms 23596 KiB
7 Elfogadva 12ms 23824 KiB
subtask3 10/10
8 Elfogadva 10ms 24080 KiB
9 Elfogadva 12ms 24156 KiB
10 Elfogadva 12ms 24244 KiB
11 Elfogadva 13ms 24544 KiB
12 Elfogadva 14ms 25128 KiB
subtask4 10/10
13 Elfogadva 16ms 26088 KiB
14 Elfogadva 12ms 24404 KiB
15 Elfogadva 13ms 24748 KiB
16 Elfogadva 12ms 24820 KiB
17 Elfogadva 148ms 71880 KiB
18 Elfogadva 52ms 34496 KiB
19 Elfogadva 68ms 38356 KiB
20 Elfogadva 54ms 34808 KiB
subtask5 10/10
21 Elfogadva 18ms 26324 KiB
22 Elfogadva 13ms 24568 KiB
23 Elfogadva 13ms 24836 KiB
24 Elfogadva 13ms 24804 KiB
25 Elfogadva 93ms 54900 KiB
26 Elfogadva 17ms 26616 KiB
27 Elfogadva 18ms 26564 KiB
subtask6 60/60
28 Elfogadva 13ms 25064 KiB
29 Elfogadva 12ms 25212 KiB
30 Elfogadva 12ms 25676 KiB
31 Elfogadva 14ms 25756 KiB
32 Elfogadva 14ms 25964 KiB
33 Elfogadva 14ms 26004 KiB
34 Elfogadva 16ms 27236 KiB
35 Elfogadva 16ms 27348 KiB
36 Elfogadva 17ms 27188 KiB
37 Elfogadva 149ms 72660 KiB
38 Elfogadva 50ms 35572 KiB
39 Elfogadva 54ms 35688 KiB
40 Elfogadva 54ms 35656 KiB
41 Elfogadva 50ms 35684 KiB
42 Elfogadva 48ms 35584 KiB
43 Elfogadva 50ms 35748 KiB
44 Elfogadva 48ms 35576 KiB
45 Elfogadva 64ms 39376 KiB
46 Elfogadva 54ms 35692 KiB
47 Elfogadva 50ms 35864 KiB
48 Elfogadva 48ms 35780 KiB
49 Elfogadva 48ms 35904 KiB
50 Elfogadva 54ms 35908 KiB