Submission #37348546

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <limits>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cstdio>
#include <bitset>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <functional>
#include <stack>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>
#include <cassert>
#include <cstdlib>
using namespace std;

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF = (1<<30)-1;
const int MOD = 1e9+7;
const ll LINF = (1ll<<62)-1;

#define REP(i,n) for(int i=0;i<(n);++i)
#define COUT(x) cout<<(x)<<"\n"
#define COUT16(x) cout << fixed << setprecision(16) << (x) << "\n"

using Graph = vector<vector<int>>;

// 二部グラフ判定
vector<int> color;
bool dfs(const Graph &G, int v, int cur = 0) {
    color[v] = cur;
    for (auto next_v : G[v]) {
        // 隣接頂点がすでに色確定していた場合
        if (color[next_v] != -1) {
            if (color[next_v] == cur) return false; // 同じ色が隣接したらダメ
            continue;
        }

        // 隣接頂点の色を変えて、再帰的に探索 (一回でも false が返ってきたら false)
        if (!dfs(G, next_v , 1 - cur)) return false;
    }
    return true;
}

int main(){    
    // 頂点数と辺数
    int N, M; cin >> N >> M;

    // グラフ入力受取
    Graph G(N);
    queue<int> que;
    vector<int> visited(N),kyori(N,0);
    vector<vector<int>> ex_kyori(N); 
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        --a;--b;
        if(i==0){
            que.push(a);
            visited[a] = 1;
        }
        G.at(a).push_back(b);
        G.at(b).push_back(a);
    }

    // 探索
    color.assign(N, -1);
    bool is_bipartite = true;
    for (int v = 0; v < N; ++v) {
        if (color.at(v) != -1) continue; // v が探索済みだったらスルー
        if (!dfs(G, v)) is_bipartite = false;
    }

    if(!is_bipartite){
        COUT(0);
    }
    else{
        while(!que.empty()){
            int from = que.front();
            que.pop();
            for(int i=0;i<G.at(from).size();i++){
                int to = G.at(from).at(i);
                if(visited[to] == 0){
                    visited[to] = 1;
                    kyori[to] = kyori[from] + 1;
                    que.push(to);
                }
            }
        }
        for(int i=0;i<N;i++){
            int p = kyori[i];
            ex_kyori[p].push_back(i);
        }
        ll even=0,odd=0;
        for(int i=0;i<N;i++){
            if(i%2==0)even+=ex_kyori[i].size();
            else odd += ex_kyori[i].size();
        }
        ll count = 0;
        for(int i=0;i<N;i++){
            if(visited[i]==0)count += N-1;
            else{
                if(kyori[i]%2==0)count += odd;
                else count += even;
                count -= G.at(i).size();
            }
        }
        COUT(count/2);
    }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:93:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   93 |             for(int i=0;i<G.at(from).size();i++){
      |                         ~^~~~~~~~~~~~~~~~~~

Judge Result