52182023-04-22 20:23:46Valaki2Turista járatokcpp14Hibás válasz 10/100170ms92596 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() != prv_id) {
                    comp[s.top()] = comp_cnt;
                    s.pop();
                }
            }
        }
    }
    for(const edge &e : graph[cur]) {
        if(e.id != prv_id && comp[e.id] == 0) {
            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
1Elfogadva9ms22552 KiB
2Hibás válasz17ms24840 KiB
subtask20/10
3Hibás válasz9ms22984 KiB
4Hibás válasz12ms23244 KiB
5Elfogadva12ms23584 KiB
6Elfogadva12ms23676 KiB
7Elfogadva10ms24024 KiB
subtask310/10
8Elfogadva12ms24112 KiB
9Elfogadva12ms24328 KiB
10Elfogadva12ms24660 KiB
11Elfogadva12ms24724 KiB
12Elfogadva14ms25492 KiB
subtask40/10
13Elfogadva16ms26784 KiB
14Elfogadva12ms25048 KiB
15Hibás válasz12ms25260 KiB
16Hibás válasz12ms25364 KiB
17Elfogadva153ms80600 KiB
18Elfogadva57ms40920 KiB
19Hibás válasz75ms46656 KiB
20Hibás válasz54ms43400 KiB
subtask50/10
21Hibás válasz17ms34680 KiB
22Elfogadva9ms32940 KiB
23Hibás válasz9ms32976 KiB
24Elfogadva12ms33040 KiB
25Elfogadva101ms68924 KiB
26Elfogadva17ms38112 KiB
27Elfogadva17ms38532 KiB
subtask60/60
28Elfogadva10ms36740 KiB
29Hibás válasz9ms36660 KiB
30Hibás válasz13ms36880 KiB
31Hibás válasz14ms37004 KiB
32Hibás válasz13ms37260 KiB
33Hibás válasz14ms37860 KiB
34Hibás válasz18ms38864 KiB
35Hibás válasz18ms39176 KiB
36Hibás válasz18ms39184 KiB
37Elfogadva170ms92596 KiB
38Elfogadva59ms52848 KiB
39Elfogadva54ms53820 KiB
40Elfogadva59ms54920 KiB
41Hibás válasz54ms55684 KiB
42Hibás válasz54ms56496 KiB
43Elfogadva54ms57656 KiB
44Hibás válasz54ms58480 KiB
45Hibás válasz71ms64256 KiB
46Hibás válasz54ms60900 KiB
47Hibás válasz54ms61448 KiB
48Hibás válasz57ms62460 KiB
49Elfogadva54ms63548 KiB
50Elfogadva59ms64380 KiB