52202023-04-22 22:24:15Valaki2Turista járatokcpp14Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva10ms22580 KiB
2Hibás válasz17ms25096 KiB
subtask210/10
3Elfogadva12ms23028 KiB
4Elfogadva9ms23112 KiB
5Elfogadva10ms23244 KiB
6Elfogadva9ms23372 KiB
7Elfogadva12ms23732 KiB
subtask310/10
8Elfogadva10ms23800 KiB
9Elfogadva9ms24004 KiB
10Elfogadva9ms24244 KiB
11Elfogadva13ms24636 KiB
12Elfogadva14ms25536 KiB
subtask410/10
13Elfogadva17ms26576 KiB
14Elfogadva13ms24884 KiB
15Elfogadva10ms25104 KiB
16Elfogadva12ms25472 KiB
17Elfogadva140ms72424 KiB
18Elfogadva50ms35028 KiB
19Elfogadva64ms38832 KiB
20Elfogadva57ms35128 KiB
subtask510/10
21Elfogadva18ms26856 KiB
22Elfogadva10ms25168 KiB
23Elfogadva10ms25176 KiB
24Elfogadva10ms25188 KiB
25Elfogadva96ms55288 KiB
26Elfogadva17ms26948 KiB
27Elfogadva16ms26944 KiB
subtask60/60
28Elfogadva13ms25228 KiB
29Hibás válasz10ms25364 KiB
30Hibás válasz12ms25584 KiB
31Hibás válasz12ms25808 KiB
32Elfogadva13ms25852 KiB
33Hibás válasz14ms26148 KiB
34Hibás válasz17ms27172 KiB
35Hibás válasz17ms27164 KiB
36Hibás válasz19ms27172 KiB
37Elfogadva138ms72428 KiB
38Elfogadva48ms35224 KiB
39Elfogadva54ms35468 KiB
40Elfogadva50ms35536 KiB
41Elfogadva50ms35604 KiB
42Elfogadva52ms35512 KiB
43Elfogadva52ms35496 KiB
44Elfogadva52ms35376 KiB
45Elfogadva68ms39412 KiB
46Elfogadva52ms35636 KiB
47Elfogadva52ms35804 KiB
48Elfogadva52ms35644 KiB
49Elfogadva54ms35856 KiB
50Elfogadva54ms35788 KiB