52222023-04-22 22:59:54Valaki2Turista járatokcpp14Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva10ms22548 KiB
2Elfogadva18ms24740 KiB
subtask210/10
3Elfogadva9ms22972 KiB
4Elfogadva12ms23160 KiB
5Elfogadva12ms23500 KiB
6Elfogadva9ms23596 KiB
7Elfogadva12ms23824 KiB
subtask310/10
8Elfogadva10ms24080 KiB
9Elfogadva12ms24156 KiB
10Elfogadva12ms24244 KiB
11Elfogadva13ms24544 KiB
12Elfogadva14ms25128 KiB
subtask410/10
13Elfogadva16ms26088 KiB
14Elfogadva12ms24404 KiB
15Elfogadva13ms24748 KiB
16Elfogadva12ms24820 KiB
17Elfogadva148ms71880 KiB
18Elfogadva52ms34496 KiB
19Elfogadva68ms38356 KiB
20Elfogadva54ms34808 KiB
subtask510/10
21Elfogadva18ms26324 KiB
22Elfogadva13ms24568 KiB
23Elfogadva13ms24836 KiB
24Elfogadva13ms24804 KiB
25Elfogadva93ms54900 KiB
26Elfogadva17ms26616 KiB
27Elfogadva18ms26564 KiB
subtask660/60
28Elfogadva13ms25064 KiB
29Elfogadva12ms25212 KiB
30Elfogadva12ms25676 KiB
31Elfogadva14ms25756 KiB
32Elfogadva14ms25964 KiB
33Elfogadva14ms26004 KiB
34Elfogadva16ms27236 KiB
35Elfogadva16ms27348 KiB
36Elfogadva17ms27188 KiB
37Elfogadva149ms72660 KiB
38Elfogadva50ms35572 KiB
39Elfogadva54ms35688 KiB
40Elfogadva54ms35656 KiB
41Elfogadva50ms35684 KiB
42Elfogadva48ms35584 KiB
43Elfogadva50ms35748 KiB
44Elfogadva48ms35576 KiB
45Elfogadva64ms39376 KiB
46Elfogadva54ms35692 KiB
47Elfogadva50ms35864 KiB
48Elfogadva48ms35780 KiB
49Elfogadva48ms35904 KiB
50Elfogadva54ms35908 KiB