Submission #74230513

---

Source Code Expand

#include <bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<long long> vll;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#define endl '\n'
ll mod = 1e9+7 ;
int p1 = 31 , p2 = 91 ;
ll mod1= 1e9+7 , mod2 = 1e9+9 ;

void dfs(int node , int parent , vector<vector<int>>& adj , vector<int>&visited, int cur ,vector<int>&depth) {
    visited[node] = cur ;
    depth[node] = depth[parent] + 1;
    for(auto it : adj[node]) {
        if(it == parent) continue ;
        if(!visited[it]) dfs(it, node, adj , visited, cur, depth) ;
    }


}
bool dfs1(int node , int parent , vector<int>&colored , vector<vector<int>> &adj) {
    if(node == parent) colored[node] = 0 ;
    else colored[node] = colored[parent]^1 ;
    bool test = 1 ;
    for(auto it : adj[node]) {
        if(it == parent) continue ;
        if(colored[it ] == -1) test&=dfs1(it, node , colored , adj);
        else {
            if(colored[it] == colored[node]) return 0 ;
        }
    }
    return test ;
}

void solve() {
    int n , m ; cin >> n >>  m ;
    vector<vector<int>> adj(n) ;
    for(int i = 0 ; i < m ; ++i) {
        int u , v ; cin>> u >> v ;
        u-- ;v-- ;
        adj[u].push_back(v);
        adj[v].push_back(u) ;
    }
    vector<int> visited(n,0) ;

    vector<vector<int>> adj2 = adj ;
    vector<int> colored (n,-1) ;
    bool test = 1 ;
    for(int i = 0 ; i < n ;++i) {
        if(colored[i] == -1) test&=dfs1(i,i,colored ,adj2 );
    }
    if(!test) {
        cout << 0 << endl ;
    }else{
        vector<int> depth(n,-1) ;
        int cur = 1 ;
        ll ans = 0 ;
        for(int i = 0 ; i < n ; ++i) {
            if(!visited[i]) {
                dfs(i,i , adj , visited , cur , depth);
                cur ++;
            }
        }
        // for(auto it : visited) cout << it << ' ' ;
        // cout << endl ;
        // for(auto it : depth) cout << it << ' ' ;
        // cout << endl ;
        map<int,pair<ll,ll>> mp ;
        for(int i = 0 ; i <  n ;++i) {
            if(depth[i]%2) mp[visited[i]].first++;
            else mp[visited[i]].second++;
        }
        ans -= m ;
        ll ans1 = 0 ;
        for(auto it : mp) {
            ans += it.second.second * it.second.first ;
            ans1+= 1ll* (it.second.second + it.second.first) * (n - (it.second.second + it.second.first) ) ;
        }
        cout << ans +ans1/2 << endl ;
    }
}




int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Submission Info

Judge Result