Algorithm

USACO Section5.3 schlnet

Problem Summary

Given a software distribution network of schools, i.e. a directed graph, compute :

  1. The minimal number of shools that must receive a copy of the new software in order for it to reach all schools.

  2. The minimal number of extensions (i.e. edges) that have to be made so that whatever school we send the new software to, it will reach all other schools.

Analysis & Solution

At first, we need to know the concept of strongly connected component. This is its defination on Wikipedia :

In the mathematical theory of directed graphs, a graph is said to be strongly connected or diconnected if every vertex is reachable from every other vertex. The strongly connected components or diconnected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected.

Apparently, when a school,i.e. a vertex, is given a copy of the software, all the vertices that are strongly connected to it will have access to the software.
So we can use Tarjan’s algorithm to find all strongly connected components, and “shrink” all components into vertices. Then we have a new graph, which is either a single vertex, or a DAG without any strongly connected components.

Now subtask 1 is actually finding the number of vertices that have zero indegree.
Subtast 2 is about how to make this new graph strongly connected. If it is already a single vertex, there is no need to add any edge. If it is a DAG, we can do this greedily. We only need to eliminate all vertices with zero indegree and those with zero outdegree (suppose the number of them are respectively A and B). Then we only have to add max(A,B) edges.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 102;
int n;
bool g[maxn][maxn];
int top=0,stack[maxn];
bool in_satck[maxn];
int idx=0,dfn[maxn],low[maxn];
int tot=0,color[maxn];
int in_degree[maxn],out_degree[maxn];
void tarjan(int cur)
{
	idx++;
	dfn[cur]=low[cur]=idx;
	top++;
	stack[top]=cur;
	in_satck[cur]=true;
	for(int i=1;i<=n;i++)
		if(g[cur][i])
		{
			if(dfn[i]==0)
			{
				tarjan(i);
				low[cur]=min(low[cur],low[i]);
			}
			else
			if(in_satck[i])
				low[cur]=min(low[cur],dfn[i]);
		}
	if(low[cur]==dfn[cur])
	{
		tot++;
		int j;
		do{
			j=stack[top];
			color[j]=tot;
			in_satck[j]=false;
			top--;
		}while(j!=cur);
	}
}
int main()
{
	fstream fin("schlnet.in",ios::in);
	fstream fout("schlnet.out",ios::out);
	fin>>n;
	int t;
	for(int i=1;i<=n;i++)
		while(true)
		{
			fin>>t;
			if(t==0) break;
			g[i][t]=true;
		}
	for(int i=1;i<=n;i++)
		if(dfn[i]==0)
			tarjan(i);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(g[i][j] && color[i]!=color[j])
			{
				in_degree[color[j]]++;
				out_degree[color[i]]++;
			}
	int ans1=0,ans2=0;
	for(int i=1;i<=tot;i++)
	{
		if(in_degree[i]==0) ans1++;
		if(out_degree[i]==0) ans2++;
	}
	fout<<ans1<<endl;
	if(tot==1)
		fout<<0<<endl;
	else
	{
		ans2=ans2>ans1 ? ans2:ans1;
		fout<<ans2<<endl;
	}
	fin.close();
	fout.close();
	return 0;
}