52192023-04-22 21:36:48Valaki2Turista járatokcpp14Hibás válasz 30/100158ms71412 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];

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;
    int lowcheck = 0;
    for(const edge &e : graph[cur]) {
        int nei = e.to;
        if(!vis_low[nei]) {
            cnt++;
            dfs_low(nei, cur);
            low[cur] = min(low[cur], low[nei]);
            lowcheck = max(lowcheck, low[nei]);
        } else if(nei != par) {
            low[cur] = min(low[cur], dep[nei]);
        }
    }
    if((par == -1 && cnt > 1) || ((par != -1) && (lowcheck >= dep[cur]) && (cnt > 0))) {
        cut[cur] = true;
    }
}

stack<int> s;
int comp_cnt;
int start[1 + maxc];
int comp[1 + maxm];
int nodes_comp[1 + maxn];

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
1Elfogadva13ms22548 KiB
2Hibás válasz19ms24936 KiB
subtask210/10
3Elfogadva10ms23064 KiB
4Elfogadva9ms23016 KiB
5Elfogadva9ms23280 KiB
6Elfogadva9ms23492 KiB
7Elfogadva9ms23708 KiB
subtask30/10
8Hibás válasz9ms23664 KiB
9Elfogadva9ms23780 KiB
10Elfogadva9ms23868 KiB
11Elfogadva9ms24092 KiB
12Elfogadva14ms24964 KiB
subtask410/10
13Elfogadva17ms26144 KiB
14Elfogadva12ms24540 KiB
15Elfogadva13ms24728 KiB
16Elfogadva13ms25056 KiB
17Elfogadva157ms70784 KiB
18Elfogadva57ms34784 KiB
19Elfogadva68ms38468 KiB
20Elfogadva57ms34912 KiB
subtask510/10
21Elfogadva17ms27064 KiB
22Elfogadva12ms25516 KiB
23Elfogadva12ms25632 KiB
24Elfogadva10ms25568 KiB
25Elfogadva87ms55556 KiB
26Elfogadva16ms27284 KiB
27Elfogadva17ms27252 KiB
subtask60/60
28Elfogadva10ms25548 KiB
29Hibás válasz10ms25696 KiB
30Hibás válasz13ms25900 KiB
31Hibás válasz14ms26264 KiB
32Hibás válasz14ms26344 KiB
33Hibás válasz16ms26472 KiB
34Hibás válasz17ms27660 KiB
35Hibás válasz17ms27600 KiB
36Hibás válasz17ms27600 KiB
37Elfogadva158ms71412 KiB
38Elfogadva57ms35540 KiB
39Elfogadva57ms35400 KiB
40Elfogadva54ms35652 KiB
41Elfogadva57ms35640 KiB
42Elfogadva57ms35608 KiB
43Elfogadva56ms35608 KiB
44Elfogadva54ms35596 KiB
45Elfogadva68ms39372 KiB
46Elfogadva54ms35644 KiB
47Elfogadva57ms35816 KiB
48Elfogadva57ms35620 KiB
49Elfogadva57ms35620 KiB
50Elfogadva56ms35624 KiB