缩点

首先第一个任务,我们要找到至少应该发布任务的点数。
我们很清楚的一点:如果这个图是一个DAG的话,我们只要在入度数为0的点处放置就可以了。
但是在所给的测试样例中,我们可以看到节点1在一个环中。我们会注意到,在这个环中无论在那个点放置都可以
到达所有的点。那边给了我们思路,我们先缩点,将图变为一个DAG。
然后第一个答案就是此是入度为0的缩点数。

那第二个答案呢?我们要选择连最少的边使得整个图都是一个强连通分量。
我在这里WA了五发。实在是痛苦。情况一定要考虑好。
推荐看这篇博客:
https://xiaoxiaoh.blog.csdn.net/article/details/104284558

代码如下:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
struct edge{
    int to, next;
}E[20000];
int head[110];
int cnt = 1;
void add(int from, int to) {
    E[cnt].to = to;E[cnt].next = head[from];
    head[from] = cnt++;
}

int dfn[110], low[110];
int color[110];
int tot = 0, colour = 0;
stack<int> st;
void tarjan(int u) {
    dfn[u] = low[u] = ++tot;st.push(u);
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (color[v] == 0)low[u] = min(low[u], dfn[v]);
    }if (low[u] != dfn[u] )return;
    ++colour;
    while (st.top() != u) {
        color[st.top()] = colour;
        st.pop();
    }color[st.top()] = colour;st.pop();
}

int n;
bool in[110];
bool out[110];
int main() {
    scanf("%d", &n);
    for (int i = 1, j;i <= n;++i) {
        while (scanf("%d", &j)) {
            if (j == 0)break;
            add(i, j);
        }
    }
    for (int i = 1;i <= n;++i)
        if (!dfn[i])
            tarjan(i);
    for (int u = 1;u <= n;++u) {
        for (int i = head[u];i;i = E[i].next) {
            int v = E[i].to;
            if (color[u] != color[v]) {
                out[color[u]] = true;
                in[color[v]] = true;
            }
        }
    }int cnt1 = 0;int cnt2 = 0;
    for (int i = 1;i <= colour;++i) {
        if (!in[i])++cnt1;
        if (!out[i])++cnt2;
    }printf("%d\n", cnt1);
    if (colour == 1)printf("0");
    else printf("%d", max(cnt1, cnt2));
}