Submission #39463735

Source Code Expand

#include<bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> u(M), v(M);
  for(int i = 0; i < M; ++i){
    cin >> u[i] >> v[i];
    u[i]--, v[i]--;
  }

  dsu uf(N);
  for(int i = 0; i < M; ++i) uf.merge(u[i], v[i]);

  // それぞれの頂点がどの連結成分に属するかを求める
  vector<int> groupId(N);
  for(int i = 0; i < N; ++i) groupId[i] = uf.leader(i);

  // それぞれの連結成分に含まれる頂点数を数える
  vector<int> groupVertexNum(N, 0);
  for(int i = 0; i < N; ++i) groupVertexNum[groupId[i]]++;

  // それぞれの連結成分に含まれる辺数を数える
  vector<int> groupEdgeNum(N, 0);
  for(int i = 0; i < M; ++i) groupEdgeNum[groupId[u[i]]]++;

  // それぞれの連結成分で頂点数と辺数が一致しないものがあればNo
  for(int i = 0; i < N; ++i){
    if(groupVertexNum[i] != groupEdgeNum[i]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Submission Info

Submission Time
Task D - Unicyclic Components
User dokaraya
Language C++ (GCC 9.2.1)
Score 400
Code Size 1077 Byte
Status AC
Exec Time 94 ms
Memory 8040 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 61
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 02_one_00.txt, 02_one_01.txt, 02_one_02.txt, 02_one_03.txt, 02_one_04.txt, 02_one_05.txt, 02_one_06.txt, 02_one_07.txt, 02_one_08.txt, 02_one_09.txt, 02_one_10.txt, 02_one_11.txt, 02_one_12.txt, 02_one_13.txt, 03_two_00.txt, 03_two_01.txt, 03_two_02.txt, 03_two_03.txt, 03_two_04.txt, 03_two_05.txt, 03_two_06.txt, 03_two_07.txt, 03_two_08.txt, 03_two_09.txt, 03_two_10.txt, 03_two_11.txt, 04_many_00.txt, 04_many_01.txt, 04_many_02.txt, 04_many_03.txt, 04_many_04.txt, 04_many_05.txt, 04_many_06.txt, 04_many_07.txt, 04_many_08.txt, 04_many_09.txt, 04_many_10.txt, 04_many_11.txt, 05_hand_00.txt, 05_hand_01.txt, 99_hack_00.txt, 99_hack_01.txt, 99_hack_02.txt, 99_hack_03.txt, 99_hack_04.txt, 99_hack_05.txt, 99_hack_06.txt, 99_hack_07.txt, 99_hack_08.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 8 ms 3592 KiB
00_sample_01.txt AC 2 ms 3512 KiB
00_sample_02.txt AC 3 ms 3520 KiB
01_rnd_00.txt AC 2 ms 3576 KiB
01_rnd_01.txt AC 2 ms 3516 KiB
01_rnd_02.txt AC 53 ms 4636 KiB
01_rnd_03.txt AC 2 ms 3672 KiB
01_rnd_04.txt AC 2 ms 3584 KiB
01_rnd_05.txt AC 64 ms 4780 KiB
01_rnd_06.txt AC 10 ms 6300 KiB
01_rnd_07.txt AC 7 ms 6364 KiB
01_rnd_08.txt AC 94 ms 7960 KiB
02_one_00.txt AC 4 ms 3512 KiB
02_one_01.txt AC 2 ms 3464 KiB
02_one_02.txt AC 2 ms 3576 KiB
02_one_03.txt AC 2 ms 3504 KiB
02_one_04.txt AC 2 ms 3616 KiB
02_one_05.txt AC 2 ms 3652 KiB
02_one_06.txt AC 2 ms 3592 KiB
02_one_07.txt AC 83 ms 7860 KiB
02_one_08.txt AC 82 ms 7952 KiB
02_one_09.txt AC 81 ms 7948 KiB
02_one_10.txt AC 81 ms 8032 KiB
02_one_11.txt AC 81 ms 7984 KiB
02_one_12.txt AC 83 ms 7804 KiB
02_one_13.txt AC 86 ms 7948 KiB
03_two_00.txt AC 82 ms 8036 KiB
03_two_01.txt AC 82 ms 7828 KiB
03_two_02.txt AC 83 ms 7800 KiB
03_two_03.txt AC 81 ms 7972 KiB
03_two_04.txt AC 81 ms 7800 KiB
03_two_05.txt AC 83 ms 7824 KiB
03_two_06.txt AC 87 ms 8036 KiB
03_two_07.txt AC 82 ms 7976 KiB
03_two_08.txt AC 82 ms 7984 KiB
03_two_09.txt AC 81 ms 7944 KiB
03_two_10.txt AC 82 ms 7912 KiB
03_two_11.txt AC 82 ms 7960 KiB
04_many_00.txt AC 62 ms 6564 KiB
04_many_01.txt AC 62 ms 6640 KiB
04_many_02.txt AC 62 ms 6712 KiB
04_many_03.txt AC 61 ms 6628 KiB
04_many_04.txt AC 81 ms 7804 KiB
04_many_05.txt AC 82 ms 8040 KiB
04_many_06.txt AC 82 ms 7936 KiB
04_many_07.txt AC 82 ms 7872 KiB
04_many_08.txt AC 79 ms 7620 KiB
04_many_09.txt AC 79 ms 7688 KiB
04_many_10.txt AC 78 ms 7540 KiB
04_many_11.txt AC 78 ms 7712 KiB
05_hand_00.txt AC 2 ms 3444 KiB
05_hand_01.txt AC 90 ms 7884 KiB
99_hack_00.txt AC 4 ms 3656 KiB
99_hack_01.txt AC 2 ms 3440 KiB
99_hack_02.txt AC 2 ms 3564 KiB
99_hack_03.txt AC 3 ms 3516 KiB
99_hack_04.txt AC 2 ms 3436 KiB
99_hack_05.txt AC 2 ms 3628 KiB
99_hack_06.txt AC 2 ms 3516 KiB
99_hack_07.txt AC 2 ms 3596 KiB
99_hack_08.txt AC 3 ms 3440 KiB