Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- //#include <chrono>
- //#include <fstream>
- //#include <bits/stdc++.h>
- #include <vector>
- #include <algorithm>
- #define mp make_pair
- #define pb push_back
- #define eb emplace_back
- #define f first
- #define s second
- #define sz(x) (int)x.size()
- #define all(x) begin(x), end(x)
- #define rall(x) rbegin(x), rend(x)
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pi;
- typedef pair<ll, ll> pl;
- int count_bridge = 0;
- int timer = 0;
- int n, m;
- vector<vector<bool>> vec;
- vector<int> tin;
- vector<int> fup;
- vector<bool> used;
- void dfs(int cur_v, int p) {
- used[cur_v] = true;
- fup[cur_v] = tin[cur_v] = timer++;
- for (int i = 0; i < n; i++) {
- if (i == p) continue;
- if (vec[cur_v][i] && used[i]) fup[cur_v] = min(fup[cur_v], tin[i]);
- else if (vec[cur_v][i]) {
- dfs(i, cur_v);
- fup[cur_v] = min(fup[cur_v], fup[i]);
- if (fup[i] > tin[cur_v])
- count_bridge++;
- }
- }
- }
- int main() {
- /*ifstream cin("in.txt");
- ofstream cout("out.txt");
- auto start_time = chrono::high_resolution_clock::now();*/
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- cin >> n >> m;
- vec.assign(n, vector<bool>(n));
- tin.assign(n, 0);
- fup.assign(n, 0);
- used.assign(n, false);
- for (int i = 0; i < m; i++) {
- int a, b;
- cin >> a >> b;
- vec[--a][--b] = true;
- vec[b][a] = true;
- }
- for (int i = 0; i < n; i++)
- if (!used[i])
- dfs(i, -1);
- cout << m - count_bridge << "\n";
- /*auto end_time = chrono::high_resolution_clock::now();
- chrono::duration<double> duration = end_time - start_time;
- cout << duration.count() << "\n";
- cin.close();
- cout.close();*/
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement