Revision en2, by visheshgautam.official, 2023-04-20 10:14:13

# include <bits/stdc++.h>

using namespace std;[contest:https://atcoder.jp/contests/abc282/tasks/abc282_d] map<int, list> mp; int colour[200005]; bool vis[200005]; bool bip = true; long long int ans=0; long long int ct=0; void colcomp(long long x, long long c); void init() { for (int i = 0; i < 200005; i++) { colour[i] = -1; vis[i] = false; } } void travel(long long n) {

for (int i = 1; i <= n; i++)
{
ct=1;
if (vis[i] == false)
{
colcomp(i, 1);
}
if(ct!=1){
long long  int k=ct/2;
long long int c1=k;
long long int c2=k+ct%2;
ans-=(c1*(c1-1))/2;
ans-=(c2*(c2-1))/2;
}
}

} void colcomp(long long x, long long c) {

vis[x] = true;
colour[x] = c;
for (auto it = mp[x].begin(); it != mp[x].end(); it++)
{
if (colour[*it] == -1){
ct++;
colcomp(*it, 1 - c);
}
else
{
if (colour[*it] == colour[x])
{
bip = false;

}
else
{
// do nothing
}
}
}

}

int main() { #define int long long int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; mp[a].push_back(b); mp[b].push_back(a); } init(); travel(n); ans-=m; ans+=(n*(n-1))/2; if(!bip){ cout<<0<<endl; return 0; } cout<<ans<<endl; }

#### History

Revisions

Rev. Lang. By When Δ Comment
en2 visheshgautam.official 2023-04-20 10:14:13 77
en1 visheshgautam.official 2023-04-20 10:13:03 1656 Initial revision (published)