Submission #4071336

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>

#define MAX_N (100000)
#define MAX_M (100000)

using namespace std;

int is_bipartite(const vector<vector<int>> &adj_lists, int cur,
                 vector<int> &gs) {
  int ret = 1;
  for (int nxt : adj_lists[cur]) {
    if (gs[nxt] == 0) {
      gs[nxt] = -gs[cur];
      if (!is_bipartite(adj_lists, nxt, gs)) {
        ret = 0;
        break;
      }
    } else {
      if (gs[nxt] == gs[cur]) {
        ret = 0;
        break;
      }
    }
  }
  return ret;
}

// read editorial
int main(int argc, char *argv[]) {
  // read inputs
  int n, m, as[MAX_M], bs[MAX_M];
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &as[i], &bs[i]);
    as[i]--;  // NOTE : modified input
    bs[i]--;  // NOTE : modified input
  }

  // create adjacency lists
  vector<vector<int>> adj_lists(n, vector<int>());
  for (int i = 0; i < m; i++) {
    const int a = as[i], b = bs[i];
    adj_lists[a].push_back(b);
    adj_lists[b].push_back(a);
  }

  // check whether the graph is bipartite
  vector<int> gs(n, 0);
  gs[0] = 1;
  const int b = is_bipartite(adj_lists, 0, gs);
  if (b) {
    int cnt_b = 0, cnt_w = 0;
    for (int g : gs) {
      if (g > 0) {
        cnt_b++;
      } else {
        cnt_w++;
      }
    }
    // printf("cnt_b = %d, cnt_w = %d\n", cnt_b, cnt_w);
    printf("%ld\n", (long) cnt_b * cnt_w - m);
  } else {
    printf("%ld\n", (long) (long) n * (n - 1) / 2 - m);
  }

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:35:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
                         ^
./Main.cpp:37:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &as[i], &bs[i]);
                                   ^

Judge Result