Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- #define MIN(x,y) {if (x > (y)) x = (y)}
- #define MAX(x,y) {if (x < (y)) x = (y)}
- using namespace std;
- const int N = 10005;
- typedef pair<int,int> ii;
- vector<int> a[N];
- int n,m,par[N];
- int num[N],low[N], cnt = 0;
- vector<ii> res;
- void dfs(int u)
- {
- low[u] = num[u] = ++ cnt;
- for(int i = 0; i < a[u].size(); ++i)
- {
- int v = a[u][i];
- if (v == par[u]) continue;
- if (par[v]) low[u]=min(low[u],num[v]);
- else
- {
- par[v]=u;
- dfs(v);
- low[u]=min(low[u],low[v]);
- if (low[v] == num[v]) res.push_back(ii(u,v));
- }
- }
- }
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- freopen("cbridge.inp","r",stdin);
- freopen("cbridge.out","w",stdout);
- cin >> n >> m;
- for(int i=1; i<=m; ++i)
- {
- int u,v;
- cin >> u >> v;
- a[u].push_back(v);
- a[v].push_back(u);
- }
- for(int i=1; i<=n; ++i)
- {
- if (!par[i])
- {
- par[i]=-1;
- dfs(i);
- }
- }
- cout << res.size() << endl;
- for(ii x : res) cout << x.first << " " << x.second << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement