题目大意：有N个点，接着给出N个点所能连接的点。 问题1：如果要将一个信息传递给这N个点，至少需要传递给多少个点，然后让这些点进行传播，使N个点都得到信息 问题2：需要添加多少条边才能使这N个点能两两连通
解题思路：求出所有的强连通分量，接着缩点，再以桥为路径，建图 找出这张图中入度为0的，因为只有入度为0的才需要进行通知，其他的点可以通过其他边进行传达
需要添加多少个点，观察这张图，，求出每个点的出度和入度，取max(入度为零的点的数量，出度为0的点数量)
注意当强连通分量只有1个的时候
min(a,b) ((a)<(b)? (a): (b))M 10010struct Edge{int from, to, next;}E[M];int head[N], sccno[N], stack[N], pre[N], lowlink[N], in[N], out[N];int n, tot, dfs_clock, scc_cnt, top;void AddEdge(int u, int v) {E[tot].from = u;E[tot].to = v;E[tot].next = head[u];head[u] = tot++;}void init() {memset(head, -1, sizeof(head));tot = 0;int v;for (int u = 1; u <= n; u++) {while (scanf(“%d”, &v) && v) AddEdge(u, v);}}void dfs(int u) {pre[u] = lowlink[u] = ++dfs_clock;stack[++top] = u;int v;for (int i = head[u]; i != -1; i = E[i].next) {v = E[i].to;if (!pre[v]) {dfs(v);lowlink[u] = min(lowlink[u], lowlink[v]);}else if (!sccno[v]) {lowlink[u] = min(lowlink[u], pre[v]);}}if (pre[u] == lowlink[u]) {scc_cnt++;while (1) {v = stack[top–];sccno[v] = scc_cnt;if (u == v)break;}}}void solve() {memset(pre, 0, sizeof(pre));memset(sccno, 0, sizeof(sccno));dfs_clock = top = scc_cnt = 0;for (int i = 1; i <= n; i++)if (!pre[i])dfs(i);if (scc_cnt == 1) {printf(“1\n0\n”);return ;}for (int i = 1; i <= scc_cnt; i++)in[i] = out[i] = 1;int u, v;for (int i = 0; i < tot; i++) {u = sccno[E[i].from];v = sccno[E[i].to];if (u != v) out[u] = in[v] = 0;}int ans1 = 0, in_num = 0, out_num = 0;for (int i = 1; i <= scc_cnt; i++) {if (in[i]) in_num++;if (out[i]) out_num++;}printf(“%d\n%d\n”, in_num, max(in_num, out_num));}int main() {while (scanf(“%d”, &n) != EOF) {init();solve();}return 0;}
而只有在充满了艰辛的人生旅途中，
