Codeforces Round #346 (Div. 2) E. New Reform

問題

codeforces.com

解法

連結成分に一つでも閉路があると, すべての頂点の入次数を 1 以上にすることが出来ます。そうでない場合は木になりますが, 一つの頂点を root として, それ以外のすべての頂点の入次数を 1 以上に出来ます。

よって, 各連結成分について閉路があるかを判定できれば良いですが, これは辺の数(edge)と頂点の数(vertex)の比較で判定できます。edge < vertex なら木, そうでないなら閉路があります。

bool done[100100];

void dfs(int now, const vector<vi>& G, vi& vs) {
    done[now] = true;
    vs.push_back(now);
    for (int next : G[now]) if (!done[next]) dfs(next, G, vs);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vi> G(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) if (!done[i]) {
        vector<int> vs;
        dfs(i, G, vs);
        int edge = 0, vertex = vs.size();
        for (int v : vs) edge += G[v].size();
        edge /= 2;
        if (edge < vertex) ans++;
    }
    cout << ans << endl;
    return 0;
}