Submission #3016256

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<signed(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
//#define EVEL 1

#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 1000000007;
const ll INF = 20000000000;
typedef std::pair<int,int> P;


	ll ans=0;
	ll N,M,K,G,A[500010],B[500010];
	ll sum;bool F=true;
	string S;
struct UnionFind {
    vector< int > data;
    UnionFind(int sz){
        data.assign(sz, -1);
    }
    bool unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return(false);
        if(data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return(true);
    }

    int find(int k){
        if(data[k] < 0) return(k);
        return(data[k] = find(data[k]));
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }
    int size(int k){
        return(-data[find(k)]);
    }
};

int main(){
	ios_base::sync_with_stdio(false);
	cin>>N>>M;
	UnionFind U(2*N);
	REP(i,M){
		int a,b;
		cin>>a>>b;a--,b--;
		U.unite(a,b+N);
		U.unite(a+N,b);
	}
	REP(i,N){
		if(U.same(i,i+N)){
			cout<<N*(N-1)/2-M;
			return 0;
		}
	}
	ll cnt=0;
	REP(i,N){
		if(U.same(0,i))cnt++;
	}
	cout<<cnt*(N-cnt)-M;
}
//連結グラフにおいてはv_a,v_bが同じ集合に属していたらそいつは二部グラフじゃない
//http://noshi91.hatenablog.com/entry/2018/04/17/183132
//https://ei1333.github.io/algorithm/union-find.html

Submission Info

Judge Result