Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #include <utility>
- #include <vector>
- #include <set>
- #include <map>
- #include <queue>
- #include <stack>
- #include <string>
- #include <cmath>
- #include <bitset>
- #include <ctime>
- #include <random>
- #include <cstdlib>
- #include <deque>
- #define F first
- #define S second
- #define pb push_back
- #define ll long long
- using namespace std;
- const int N = 2e5+5, INF = 1e9;
- const bool debug = 0;
- int n, m, a[N], b[N], tin[N], tk;
- ll ans;
- vector<int> g[N];
- bool ban[N], u[N];
- int dfs(int v, int p = 0){
- int res = tin[v] = ++tk, go;
- for(int to: g[v]){
- go = a[to]^b[to]^v;
- if(go==p) continue;
- if(tin[go]){ res = min(res,tin[go]); continue;}
- int temp = dfs(go,v);
- res = min(temp,res);
- if(temp>=tin[go]) ban[to] = 1;
- }
- return res;
- }
- int dfs2(int v){
- if(u[v]) return 0;
- int res = u[v] = 1;
- for(int i = 0; i < g[v].size(); ++i){
- if(!ban[g[v][i]]) continue;
- res+=dfs2(a[g[v][i]]^b[g[v][i]]^v);
- }
- return res;
- }
- int main(){
- if(debug) freopen("input.txt","r",stdin);
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- cin >> n >> m;
- for(int i = 1; i <= m; ++i)
- cin >> a[i] >> b[i],
- g[a[i]].pb(i),
- g[b[i]].pb(i);
- for(int i = 1; i <= n; ++i)
- if(!tin[i]) dfs(i);
- for(int i = 1; i <= n; ++i){
- ll temp = max(1,dfs2(i));
- ans += temp*(temp-1)/2-temp+1;
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement