Submission #10342872
Source Code Expand
#include <bits/stdc++.h>
#include <cmath>
const double PI = 3.14159265358979323846;
//using namespace boost::multiprecision;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 1e15;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;
std::istream &operator>>(std::istream &in, set<int> &o) {
ll a;
in >> a;
o.insert(a);
return in;
}
std::istream &operator>>(std::istream &in, queue<int> &o) {
ll a;
in >> a;
o.push(a);
return in;
}
bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }
//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
//const ll mod = 1e10;
typedef priority_queue<long long, vector<long long>, greater<long long> > PQ_ASK;
template<typename T>
struct edge {
int src, to;
T cost;
edge(int to, T cost) : src(-1), to(to), cost(cost) {}
edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
edge &operator=(const int &x) {
to = x;
return *this;
}
operator int() const { return to; }
};
template<typename T>
using Edges = vector<edge<T> >;
template<typename T>
using WeightedGraph = vector<Edges<T> >;
using UnWeightedGraph = vector<vector<int> >;
template<typename T>
using Matrix = vector<vector<T> >;
template<typename G>
struct LowLink {
const G &g;
vector<int> used, ord, low;
vector<int> articulation;
vector<pair<int, int> > bridge;
LowLink(const G &g) : g(g) {}
int dfs(int idx, int k, int par) {
used[idx] = true;
ord[idx] = k++;
low[idx] = ord[idx];
bool is_articulation = false;
int cnt = 0;
for (auto &to : g[idx]) {
if (!used[to]) {
++cnt;
k = dfs(to, k, idx);
low[idx] = min(low[idx], low[to]);
is_articulation |= ~par && low[to] >= ord[idx];
if (ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int) to));
} else if (to != par) {
low[idx] = min(low[idx], ord[to]);
}
}
is_articulation |= par == -1 && cnt > 1;
if (is_articulation) articulation.push_back(idx);
return k;
}
virtual void build() {
used.assign(g.size(), 0);
ord.assign(g.size(), 0);
low.assign(g.size(), 0);
int k = 0;
for (int i = 0; i < g.size(); i++) {
if (!used[i]) k = dfs(i, k, -1);
}
}
};
int main() {
int n, m;
cin >> n >> m;
UnWeightedGraph g(n);
rep(i, m) {
int a, b;
cin >> a >> b;
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
}
LowLink<UnWeightedGraph > lowLink(g);
lowLink.build();
cout << lowLink.bridge.size() << endl;
}
Submission Info
Submission Time |
|
Task |
C - Bridge |
User |
riku_tanide |
Language |
C++14 (GCC 5.4.1) |
Score |
300 |
Code Size |
3204 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
300 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_1.txt |
AC |
1 ms |
256 KB |
subtask_1_10.txt |
AC |
1 ms |
256 KB |
subtask_1_11.txt |
AC |
1 ms |
256 KB |
subtask_1_12.txt |
AC |
1 ms |
256 KB |
subtask_1_13.txt |
AC |
1 ms |
256 KB |
subtask_1_14.txt |
AC |
1 ms |
256 KB |
subtask_1_15.txt |
AC |
1 ms |
256 KB |
subtask_1_16.txt |
AC |
1 ms |
256 KB |
subtask_1_17.txt |
AC |
1 ms |
256 KB |
subtask_1_2.txt |
AC |
1 ms |
256 KB |
subtask_1_3.txt |
AC |
1 ms |
256 KB |
subtask_1_4.txt |
AC |
1 ms |
256 KB |
subtask_1_5.txt |
AC |
1 ms |
256 KB |
subtask_1_6.txt |
AC |
1 ms |
256 KB |
subtask_1_7.txt |
AC |
1 ms |
256 KB |
subtask_1_8.txt |
AC |
1 ms |
256 KB |
subtask_1_9.txt |
AC |
1 ms |
256 KB |