Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <stack>
- #include <set>
- #include <map>
- #define pii pair <int,int>
- using namespace std;
- using ll = long long;
- using ld = long double;
- void cv(vector <int> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvl(vector <ll> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvv(vector <vector <int> > &v){
- for (auto x: v) cv(x);
- cout<<"\n";
- }
- struct edge{
- int fr, to, id;
- };
- int n,m;
- vector <vector <edge> > G;
- const int bl = 2, gr = 1, wh = 0, inf = 2e9;
- vector <int> clr;
- void she(edge x){
- cout<<x.fr<<' '<<x.to<<' '<<x.id<<"\n";
- }
- void shG(){
- for (int i=0;i<n;++i){
- cout<<"i = "<<i<<"\n";
- for (int j = 0; j <G[i].size();++j){she(G[i][j]);}
- cout<<"\n\n";
- }
- }
- int curT = 0;
- vector <edge> bridge; //id мостов
- stack <int> comp;
- vector <int> tIn, tUp;
- void dfs(int v, int parId){//parId - id ребра по которомц пришли в v
- clr[v] = gr;
- tIn[v] = curT++;
- comp.push(v);
- cout<<"v = "<<v<<"\n";
- cout<<"clr\n";
- cv(clr);
- cout<<"tIn\n";
- cv(tIn);
- cout<<"tUp\n";
- cv(tUp);
- for (auto e: G[v]){
- if (e.id == parId) continue;
- else if (clr[e.to] == wh){
- dfs(e.to, e.id);
- tUp[v] = min(tUp[v], tUp[e.to]);
- if (tUp[e.to] >= tIn[e.to]){
- bridge.push_back(e);
- }
- }
- else if(clr[e.to] == gr){
- tUp[v] = min(tUp[v], tIn[e.to]);
- }
- }
- clr[v] = bl;
- }
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin>>n>>m;
- G.resize(n);
- clr.assign(n, wh);
- tIn.assign(n, inf);
- tUp.assign(n, inf);
- int id = 0;
- for (int i=0;i<m;++i){
- int a,b;
- cin>>a>>b;
- if (a>b) swap(a,b);
- a--; b--;
- edge any;
- any = {a, b, id};
- G[a].push_back(any);
- any = {b, a, id};
- G[b].push_back(any);
- id++;
- }
- //shG();
- for (int i = 0; i < n;++i){
- if (clr[i] == wh){
- dfs(i, -1);
- }
- }
- cout<<"ANSWER\n";
- cout<<bridge.size()<<"\n";
- for (auto i: bridge){
- cout<<i.id+1<<"\n";
- }
- cout<<"clr\n"; cv(clr);
- }
- /*
- 6 7
- 1 2
- 2 3
- 3 4
- 1 3
- 4 5
- 4 6
- 5 6
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement