test/aoj/grl/grl_3_b.test.cpp

• View this file on GitHub
• Last update: 2022-07-20 01:24:27+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B

Depends on

• 二重辺連結成分分解 (graph/two_edge_connected_components.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B"
#include <bits/stdc++.h>
using namespace std;
#include "../../../graph/two_edge_connected_components.hpp"
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int s, t;
    cin >> s >> t;
    E[s].push_back(t);
    E[t].push_back(s);
  }
  two_edge_connected_components G(E);
  vector<pair<int, int>> ans;
  for (int i = 0; i < N; i++){
    for (int j : E[i]){
      if (j > i && G[i] != G[j]){
        ans.push_back(make_pair(i, j));
      }
    }
  }
  sort(ans.begin(), ans.end());
  int cnt = ans.size();
  for (int i = 0; i < cnt; i++){
    cout << ans[i].first << ' ' << ans[i].second << endl;
  }
}

#line 1 "test/aoj/grl/grl_3_b.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B"
#include <bits/stdc++.h>
using namespace std;
#line 2 "graph/two_edge_connected_components.hpp"
/**
 * @brief 二重辺連結成分分解
*/
struct two_edge_connected_components{
  vector<int> tcc;
  int cnt = 0;
  two_edge_connected_components(vector<vector<int>> &E){
    int N = E.size();
    vector<int> p(N, -1);
    vector<int> d(N, -1);
    vector<int> imos(N, 0);
    for (int i = 0; i < N; i++){
      if (p[i] == -1){
        d[i] = 0;
        dfs1(E, p, d, imos, i);
      }
    }
    tcc = vector<int>(N, -1);
    for (int i = 0; i < N; i++){
      if (tcc[i] == -1){
        tcc[i] = cnt;
        cnt++;
        dfs2(E, p, imos, i);
      }
    }
  }
  void dfs1(vector<vector<int>> &E, vector<int> &p, vector<int> &d, vector<int> &imos, int v = 0){
    bool pe = false;
    for (int w : E[v]){
      if (w != p[v] || pe){
        if (d[w] == -1){
          p[w] = v;
          d[w] = d[v] + 1;
          dfs1(E, p, d, imos, w);
          imos[v] += imos[w];
        } else if (d[w] < d[v]){
          imos[v]++;
          imos[w]--;
        }
      } else {
        pe = true;
      }
    }
  }
  void dfs2(vector<vector<int>> &E, vector<int> &p, vector<int> &imos, int v = 0){
    for (int w : E[v]){
      if (tcc[w] == -1){
        if (imos[w] > 0){
          tcc[w] = tcc[v];
        } else {
          tcc[w] = cnt;
          cnt++;
        }
        dfs2(E, p, imos, w);
      }
    }
  }
  int operator [](int v){
    return tcc[v];
  }
};
#line 5 "test/aoj/grl/grl_3_b.test.cpp"
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int s, t;
    cin >> s >> t;
    E[s].push_back(t);
    E[t].push_back(s);
  }
  two_edge_connected_components G(E);
  vector<pair<int, int>> ans;
  for (int i = 0; i < N; i++){
    for (int j : E[i]){
      if (j > i && G[i] != G[j]){
        ans.push_back(make_pair(i, j));
      }
    }
  }
  sort(ans.begin(), ans.end());
  int cnt = ans.size();
  for (int i = 0; i < cnt; i++){
    cout << ans[i].first << ' ' << ans[i].second << endl;
  }
}

Back to top page