Codeforces #405 B. Bear and Friendship Condition

• 方針
  グラフ中の全ての部分グラフ？で
  （辺の数）= （頂点の数）*（頂点の数-1) / 2
  を満たしていれば “YES"、そうでなければ "NO"と出力。
  全探索するために配列 vis[頂点の数] を用意。 dfsでは一つの辺に対して二回ずつカウントしている。 つまり、cnt_eには本来の辺の二倍の数が格納されることになる。

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

typedef long long ll;

vector<bool> vis(150010, false);
vector<ll> g[150010];
void dfs(int a, int & cnt_v, int & cnt_e) {
    if(vis[a]) return;
    vis[a] = true;
    cnt_v++;
    cnt_e += g[a].size();

    for(int i=0;i<g[a].size();i++) {
        if(!vis[g[a][i]]) {
            dfs(g[a][i], cnt_v, cnt_e);
        }
    }
}

int main() {
    ll n, m;
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        int ai, bi;
        cin >> ai >> bi;
        ai--; bi--;
        g[ai].push_back(bi);
        g[bi].push_back(ai);
    }

    for(int i=0;i<n;i++) {
        if(!vis[i]) {
            int cnt_v = 0, cnt_e = 0;
            dfs(i, cnt_v, cnt_e);
            if(cnt_e != (ll) cnt_v * (cnt_v - 1)) {
                cout << "NO" << endl;
                //cout << cnt_e << " "<< cnt_v << endl;
                return 0;
            }
        }
    }
    cout << "YES" << endl;
}