52222023-04-22 22:59:54Valaki2Turista járatokcpp14Accepted 100/100149ms72660 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted10ms22548 KiB
2Accepted18ms24740 KiB
subtask210/10
3Accepted9ms22972 KiB
4Accepted12ms23160 KiB
5Accepted12ms23500 KiB
6Accepted9ms23596 KiB
7Accepted12ms23824 KiB
subtask310/10
8Accepted10ms24080 KiB
9Accepted12ms24156 KiB
10Accepted12ms24244 KiB
11Accepted13ms24544 KiB
12Accepted14ms25128 KiB
subtask410/10
13Accepted16ms26088 KiB
14Accepted12ms24404 KiB
15Accepted13ms24748 KiB
16Accepted12ms24820 KiB
17Accepted148ms71880 KiB
18Accepted52ms34496 KiB
19Accepted68ms38356 KiB
20Accepted54ms34808 KiB
subtask510/10
21Accepted18ms26324 KiB
22Accepted13ms24568 KiB
23Accepted13ms24836 KiB
24Accepted13ms24804 KiB
25Accepted93ms54900 KiB
26Accepted17ms26616 KiB
27Accepted18ms26564 KiB
subtask660/60
28Accepted13ms25064 KiB
29Accepted12ms25212 KiB
30Accepted12ms25676 KiB
31Accepted14ms25756 KiB
32Accepted14ms25964 KiB
33Accepted14ms26004 KiB
34Accepted16ms27236 KiB
35Accepted16ms27348 KiB
36Accepted17ms27188 KiB
37Accepted149ms72660 KiB
38Accepted50ms35572 KiB
39Accepted54ms35688 KiB
40Accepted54ms35656 KiB
41Accepted50ms35684 KiB
42Accepted48ms35584 KiB
43Accepted50ms35748 KiB
44Accepted48ms35576 KiB
45Accepted64ms39376 KiB
46Accepted54ms35692 KiB
47Accepted50ms35864 KiB
48Accepted48ms35780 KiB
49Accepted48ms35904 KiB
50Accepted54ms35908 KiB