CFR 659 E. New Reform ( DFS )

Problem - E - Codeforces
点が全て連結する場合を考えて、辺の数だけ degree = 1の点の数ができるとわかる。つまり、連結成分それぞれについてそれを求めればいい。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
typedef pair< int, int > pii;

int n, m;
pii road[ MAXM ];

int vis[ MAXN ];
int cc_cnt;
int cc_ecnt[ MAXN ];
int cc_vcnt[ MAXN ];

vector< int > G[ MAXN ];

int ex[ MAXM ];

void dfs( int u ){
    vis[ u ] = 1;
    ++cc_vcnt[ cc_cnt ];
    cc_ecnt[ cc_cnt ] += ex[ u ];
    for( int v : G[ u ] )
        if( !vis[ v ] )
            dfs( v );
}

void solve(){
    for( int i = 0; i < m; ++i ){
        G[ road[ i ].first ].push_back( road[ i ].second ),
        G[ road[ i ].second ].push_back( road[ i ].first );
        ++ex[ road[ i ].first ];
        ++ex[ road[ i ].second ];
    }
    for( int i = 1; i <= n; ++i ){
        if( vis[ i ] ) continue;
        ++cc_cnt;
        dfs( i );
        cc_ecnt[ cc_cnt ] /= 2;
    }
    int ans = 0;
    for( int i = 1; i <= cc_cnt; ++i ){
        if( cc_ecnt[ i ] < cc_vcnt[ i ] )
            ans += cc_vcnt[ i ] - cc_ecnt[ i ];
    }
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio( false );
    cin >> n >> m;
    for( int i = 0; i < m; ++i )
        cin >> road[ i ].first >> road[ i ].second;
    solve();
    return 0;
}