Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define f first
- #define s second
- #define pb push_back
- #define mp make_pair
- #define ll long long
- #define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
- using namespace std;
- const int INF = 1e9 + 1;
- const int MAXN = 4e5 + 10;
- int tin[MAXN], fup[MAXN], timer;
- bool was[MAXN];
- vector <int> ans;
- vector <pair <int, int> > g[MAXN];
- void is_bridge(int x){
- ans.pb(x);
- }
- void dfs(int v, int pr = -1){
- was[v] = 1;
- tin[v] = ++timer;
- fup[v] = tin[v];
- for (auto [to, num] : g[v]){
- if (!was[to]){
- dfs(to, v);
- fup[v] = min(fup[v], fup[to]);
- if (tin[v] < fup[to]){
- is_bridge(num);
- }
- }
- else if (to != pr){
- fup[v] = min(fup[v], tin[to]);
- }
- }
- }
- void solve(){
- int n, m;
- cin >> n >> m;
- for (int i = 1; i <= m; i++){
- int x, y;
- cin >> x >> y;
- g[x].pb({y, i});
- g[y].pb({x, i});
- }
- for (int i = 1; i <= n; i++){
- if (!was[i]){
- dfs(i);
- }
- }
- cout << ans.size() << '\n';
- sort(ans.begin(), ans.end());
- for (int x : ans){
- cout << x << ' ';
- }
- }
- int main() {
- IOS;
- freopen("bridges.in", "r", stdin);
- freopen("bridges.out", "w", stdout);
- int t = 1;
- // cin >> t;
- while(t--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment