Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- const int MAXN = 20005;
- vector<vector<int> > g(MAXN);
- bool used[MAXN];
- int timer, tin[MAXN], fup[MAXN];
- vector<pair<int,int> >ans;
- bool cmp(pair<int,int> a,pair<int,int>b)
- {
- if(a.first < b.first) return true;
- if(a.first == b.first)
- {
- return a.second < b.second;
- }
- return false;
- }
- void dfs (int v, int p = -1)
- {
- used[v] = true;
- tin[v] = fup[v] = timer++;
- for (size_t i=0; i<g[v].size(); ++i)
- {
- int to = g[v][i];
- if (to == p) continue;
- if (used[to])
- fup[v] = min (fup[v], tin[to]);
- else
- {
- dfs (to, v);
- fup[v] = min (fup[v], fup[to]);
- if (fup[to] > tin[v])
- ans.push_back({min(v,to),max(v,to)});
- }
- }
- }
- void find_bridges(int n)
- {
- timer = 0;
- for (int i=0; i<n; ++i)
- used[i] = false;
- for (int i=0; i<n; ++i)
- if (!used[i])
- dfs (i);
- }
- int main()
- {
- ifstream filei("input.txt");
- ofstream fileo("output.txt");
- int N;
- filei>>N;
- int a;
- int Count =0;
- for(int i=0; i<N; ++i)
- for(int j=0; j<N; ++j)
- {
- filei>>a;
- if(a!=0 && a!=1)
- {
- fileo<<"Error";
- return 0;
- }
- if(a==1)
- {
- Count++;
- g[i].push_back(j);
- g[j].push_back(i);
- }
- }
- find_bridges(N);
- sort(ans.begin(),ans.end(),cmp);
- fileo<<ans.size()<<endl;
- for(pair<int,int> edge:ans)
- {
- fileo<<edge.first+1<<"-"<<edge.second+1<<" ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement