771A - Bear and Friendship Condition - CodeForces Solution

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
template<typename T> 
using ordered_multiset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
template<class key, class value, class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
// less, less_equal, greater

void init_code(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif // ONLINE_JUDGE
}
 
                             // MACROS

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#define ff first
#define ss second
#define pb push_back
#define FOR(i, a, b)  for(int i=a; i<=b; i++)
#define FORR(i, a, b)  for(int i=a; i>=b; i--)  
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define vlb(v, x) lower_bound(all(v), x)
#define vub(v, x) upper_bound(all(v), x)
#define slb(v, x) v.lower_bound(x)
#define sub(v, x) v.upper_bound(x)   
#define MOD 1000000007
#define MP make_pair

// Debugging
#ifndef ONLINE_JUDGE
#include "debug.cpp"
#else
#define dbg(x)
#endif
    
                        // FUNCTIONS
ll lcm(ll a, ll b){ ll res = (a*b)/__gcd(a,b); return res; }
ll binpow(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res;}

                                // PRIMARY FUNCTION

vector<bool> vis(2e5);
vector<vector<int>> adj(2e5);
bool bad = false;

pair<int, ll> dfs(int node){
    if(vis[node])   return MP(0, 0);
    vis[node] = true;

    pair<int, ll> res;
    res.ff = 1;
    res.ss = adj[node].size();
    for(int child:adj[node]){
        pair<int, ll> x = dfs(child);
        res.ff += x.ff;
        res.ss += x.ss;
    }
    return res;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    FOR(i, 1, m){
        int x, y;
        cin >> x >> y;
        --x, --y;
        adj[x].pb(y);
        adj[y].pb(x);
    }

    FOR(i, 0, n-1){
        if(vis[i] == false){
            pair<int, ll> res = dfs(i);
            if(res.ss != res.ff*1ll*(res.ff-1)){
                cout << "NO\n";
                return;
            }
        }
    }

    cout << "YES\n";
}



 // MAIN FUNCTION
    
int main()
{
    ios_base::sync_with_stdio(0);
    init_code();

    solve();
    
    return 0;
}