52202023-04-22 22:24:15Valaki2Turista járatokcpp14Wrong answer 40/100140ms72428 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted10ms22580 KiB
2Wrong answer17ms25096 KiB
subtask210/10
3Accepted12ms23028 KiB
4Accepted9ms23112 KiB
5Accepted10ms23244 KiB
6Accepted9ms23372 KiB
7Accepted12ms23732 KiB
subtask310/10
8Accepted10ms23800 KiB
9Accepted9ms24004 KiB
10Accepted9ms24244 KiB
11Accepted13ms24636 KiB
12Accepted14ms25536 KiB
subtask410/10
13Accepted17ms26576 KiB
14Accepted13ms24884 KiB
15Accepted10ms25104 KiB
16Accepted12ms25472 KiB
17Accepted140ms72424 KiB
18Accepted50ms35028 KiB
19Accepted64ms38832 KiB
20Accepted57ms35128 KiB
subtask510/10
21Accepted18ms26856 KiB
22Accepted10ms25168 KiB
23Accepted10ms25176 KiB
24Accepted10ms25188 KiB
25Accepted96ms55288 KiB
26Accepted17ms26948 KiB
27Accepted16ms26944 KiB
subtask60/60
28Accepted13ms25228 KiB
29Wrong answer10ms25364 KiB
30Wrong answer12ms25584 KiB
31Wrong answer12ms25808 KiB
32Accepted13ms25852 KiB
33Wrong answer14ms26148 KiB
34Wrong answer17ms27172 KiB
35Wrong answer17ms27164 KiB
36Wrong answer19ms27172 KiB
37Accepted138ms72428 KiB
38Accepted48ms35224 KiB
39Accepted54ms35468 KiB
40Accepted50ms35536 KiB
41Accepted50ms35604 KiB
42Accepted52ms35512 KiB
43Accepted52ms35496 KiB
44Accepted52ms35376 KiB
45Accepted68ms39412 KiB
46Accepted52ms35636 KiB
47Accepted52ms35804 KiB
48Accepted52ms35644 KiB
49Accepted54ms35856 KiB
50Accepted54ms35788 KiB