結果

問題 No.1605 Matrix Shape
コンテスト
ユーザー SSRS
提出日時 2021-07-16 21:28:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 206 ms / 2,000 ms
コード長 1,341 bytes
コンパイル時間 1,775 ms
コンパイル使用メモリ 177,420 KB
実行使用メモリ 17,404 KB
最終ジャッジ日時 2024-07-06 08:19:02
合計ジャッジ時間 5,855 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> H(N), W(N);
  for (int i = 0; i < N; i++){
    cin >> H[i] >> W[i];
    H[i]--;
    W[i]--;
  }
  int V = 200000;
  vector<vector<int>> E(V);
  for (int i = 0; i < N; i++){
    E[H[i]].push_back(W[i]);
    E[W[i]].push_back(H[i]);
  }
  vector<bool> used(V, false);
  used[H[0]] = true;
  queue<int> Q;
  Q.push(H[0]);
  while (!Q.empty()){
    int v = Q.front();
    Q.pop();
    for (int w : E[v]){
      if (!used[w]){
        used[w] = true;
        Q.push(w);
      }
    }
  }
  bool ok = true;
  for (int i = 0; i < N; i++){
    if (!used[H[i]] || !used[W[i]]){
      ok = false;
    }
  }
  if (!ok){
    cout << 0 << endl;
  } else {
    vector<int> in(V, 0), out(V, 0);
    for (int i = 0; i < N; i++){
      out[H[i]]++;
      in[W[i]]++;
    }
    int cnt1 = 0;
    int cnt2 = 0;
    for (int i = 0; i < V; i++){
      if (in[i] - out[i] >= 2){
        ok = false;
      }
      if (out[i] - in[i] >= 2){
        ok = false;
      }
      if (in[i] - out[i] == 1){
        cnt1++;
      }
      if (in[i] > 0){
        cnt2++;
      }
    }
    if (!ok){
      cout << 0 << endl;
    } else if (cnt1 >= 2){
      cout << 0 << endl;
    } else if (cnt1 == 1){
      cout << 1 << endl;
    } else {
      cout << cnt2 << endl;
    }
  }
}
0