题目描述

难度分:$1600$

输入$n(2 \leq n \leq 10^5)$，$m(1 \leq m \leq 10^5)$表示一个$n$点$m$边的无向图（节点编号从 $1$开始）。

然后输入$m$条无向边。保证图中无自环和重边。图不一定连通。

你需要把每条边都变成有向边（定向）。定向后，入度为$0$的点最少有多少个？

输入样例$1$

4 3
2 1
1 3
4 3

输出样例$1$

1

输入样例$2$

5 5
2 1
1 3
2 3
2 5
4 3

输出样例$2$

0

输入样例$3$

6 5
1 2
2 3
4 5
4 6
5 6

输出样例$3$

1

算法

分类讨论+构造

这个题的思路还是很简单的，上午交了一发结果WA了，出去过完节回来接着想发现漏考虑了孤立点。根据$3$个样例就可以发现总共只有两种情况：

1. 连通分量没有环，那就是个无向树，定向后的最优解就只有根节点的入度是为$0$的，答案为$1$。
2. 连通分量有环，根据原题中对样例$2$的解释，发现一定可以构造出一个有向图，不存在入度为$0$的节点，多加几个环也一样。

所以利用并查集可以得到每个节点属于哪个连通分量。然后遍历每个连通分量，这个连通分量如果有环，对答案就没有贡献；否则对答案的贡献就是$1$。但是需要注意连通分量为孤立点的情况（即连通分量不一定要有边），记得考虑。

复杂度分析

时间复杂度

遍历边集可以将每个节点划分到不同的连通分量，时间复杂度为$O(mlog_2m)$。然后对每个连通分量判环，可以用DFS，也可以用$Kruskal$算法，这里我用的后者，时间复杂度也为$O(mlog_2m)$。最后判断孤立点，此时只需要判断节点$i$是否不属于任何一个有边的连通分量，如果存在这样的孤立点，就对答案自增，时间复杂度为$O(n)$。

综上，算法整体的时间复杂度为$O(mlog_2m+n)$。

空间复杂度

空间消耗主要在于并查集的父节点数组$p$，空间复杂度为$O(n)$。而整个图的邻接表空间消耗为$O(n+m)$，这个空间消耗是更大的。综上，整个算法的额外空间复杂度为$O(n+m)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;
typedef pair<int, int> PII;

const int N = 100001;
int n, m, u, v, p[N];
unordered_map<int, vector<PII>> groups;

int find(int x) {
    return p[x] == x? x: p[x] = find(p[x]);
}

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if(rx != ry) {
        p[rx] = ry;
    }
}

bool hasCycle(int u, unordered_map<int, vector<int>>& graph) {
    for(auto&edge: groups[u]) {
        int u = edge.first, v = edge.second;
        p[u] = u;
        p[v] = v;
    }
    for(auto&edge: groups[u]) {
        int u = edge.first, v = edge.second;
        if(find(u) == find(v)) {
            return true;
        }
        merge(u, v);
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        p[i] = i;
    }
    vector<PII> edges;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        edges.push_back({u, v});
        merge(u, v);
    }
    groups.clear();
    unordered_map<int, unordered_map<int, vector<int>>> graphs;
    for(auto&edge: edges) {
        int u = edge.first, v = edge.second;
        int root = find(u);
        groups[root].push_back({u, v});
        graphs[root][u].push_back(v);
        graphs[root][v].push_back(u);
    }
    int ans = 0;
    for(auto&[root, graph]: graphs) {
        if(!hasCycle(root, graph)) {
            ans++;
        }
    }
    for(auto&edge: edges) {
        int u = edge.first, v = edge.second;
        merge(u, v);
    }
    for(int i = 1; i <= n; i++) {
        if(graphs.find(i) == graphs.end() && p[i] == i) {
            ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}