题目大意:有向关系体现在电脑可以通过网络单向的传输文件,并规定一旦有电脑存在该文件,那么所有它能传输的电脑就能在第一时间得到这个文件,题目有两个问题,第一个是最少向网络中的几台电脑投放文件,能使得整个图中的电脑都得到文件,第二个问题是要最少再连接几条边,使得任意向图中一点投放文件,其他所有电脑都能得到文件。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<vector>
#define MAX 100+10
using namespace std;
vector<int> gra[MAX], N_gra[MAX];
int dfn[MAX];
int low[MAX];
int stack[MAX];
int scc[MAX];
int on_stack[MAX];
int Time;
int sta_index;
int scc_index;
int n;
int ind[MAX];
int out[MAX];
void Init() {
memset(ind, 0, sizeof(ind));
memset(out, 0, sizeof(out));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(on_stack, 0, sizeof(on_stack));
memset(stack, 0, sizeof(stack));
Time = 0;
sta_index = 0;
scc_index = 0;
}
void Tarjan(int u) {
dfn[u] = low[u] = ++Time;
stack[sta_index++] = u;
on_stack[u] = 1;
for (size_t i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if (!dfn[v]) {
Tarjan(v);
if (low[v] < low[u])
low[u] = low[v];
}
else if (on_stack[v] && dfn[v] < low[u]) {
low[u] = dfn[v];
}
}
if (low[u] == dfn[u]) {
int tmp = 0;
scc_index++;
while (u != tmp) {
tmp = stack[--sta_index];
on_stack[tmp] = 0;
scc[tmp] = scc_index;
}
}
return;
}
void Find_all_scc() {
Init();
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
Tarjan(i);
}
}
//缩点
for (int i = 1; i <= n; i++) {
for (size_t j = 0; j < gra[i].size(); j++) {
int k = gra[i][j];
if (scc[i] != scc[k]) {
ind[scc[k]]++;
out[scc[i]]++;
N_gra[scc[i]].push_back(scc[k]);
}
}
}
}
int main(void) {
scanf("%d", &n);
int t;
for (size_t i = 0; i < n; i++) {
gra[i].clear();
N_gra[i].clear();
}
for (int i = 1; i <= n; i++) {
while (scanf("%d", &t) && t) {
gra[i].push_back(t);
}
}
Find_all_scc();
if (scc_index == 1) {
printf("1\n0\n");
return 0;
}
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= scc_index; i++) {
if (ind[i] == 0)
ans1++;
if (out[i] == 0)
ans2++;
}
printf("%d\n%d\n", ans1, max(ans1, ans2));
return 0;
}