缩点
首先第一个任务,我们要找到至少应该发布任务的点数。
我们很清楚的一点:如果这个图是一个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)); }