fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl "\n"
  4. #define ll long long
  5. #define faster() ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  6. const int MOD = 1e9 + 7 ;
  7.  
  8. int n  , m ;
  9. vector<int> ke[100005];
  10. bool visited[100005] ;
  11. vector<int> tplt[200005];
  12. int idx = 1 ;
  13. void DFS(int u){
  14.     visited[u] = true ;
  15.     tplt[idx].push_back(u);
  16.     for(int v : ke[u]){
  17.         if(!visited[v]){
  18.             DFS(v);
  19.         }
  20.     }
  21. }
  22.  
  23. void solve(){
  24.     cin >> n >> m ;
  25.     for(int i = 1 ; i <= m ; i++){
  26.         int x , y ; cin >> x >> y ;
  27.         ke[x].push_back(y);
  28.         ke[y].push_back(x);
  29.     }
  30.  
  31.     for(int i = 1 ; i <= n ; i++){
  32.         if(!visited[i]){
  33.             DFS(i); // tim so thanh phan lien thong
  34.             ++idx ;
  35.         }
  36.     }
  37.  
  38.     for(int i = 1 ; i <= idx ; i++){
  39.         for(int x : tplt[i]){ // duyet tung phan tu cua tung tplt
  40.             if(tplt[i].size() - 1 != ke[x].size()){
  41.                 cout << "NO" << endl;
  42.                 return ;
  43.             }
  44.         }
  45.     }
  46.     cout << "YES" << endl;
  47.  
  48. }
  49.  
  50. int main() {
  51.     faster(); 
  52.     int test = 1 ; 
  53.     // cin >> test ;
  54.     while(test--)   solve();
  55.     return 0;
  56. }
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
Success #stdin #stdout 0.01s 10648KB
comments (?)
stdin
copy 
4 3
1 3
3 4
1 4
stdout
copy 
YES
https://ideone.com/A8hY3Z
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!