Network of Schools
IOI '96 Day 1 Problem 3
A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the "receiving schools"). Note that if B is in the distribution list of school
A, then A does not necessarily appear in the list of school B.
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure
that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be
made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.
PROGRAM NAME: schlnet
INPUT FORMAT
The first line of the input file contains an integer N: the number of schools in the network (2<=N<=100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers
of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.
SAMPLE INPUT (file schlnet.in)
5
2 4 3 0
4 5 0
0
0
1 0
OUTPUT FORMAT
Your program should write two lines to the output file. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.
SAMPLE OUTPUT (file schlnet.out)
1
2
--------------------------------------------------------------------------------
算法：强联通分支，双联通分支
首先使用强联通分子算法，把同一个分支变成一个点，然后把有向图当成无向图，求得双联通分支。
求出每一个联通分量的入度为0的点和出度为0的点。
task A很好求，只需要把所有的入度为0的点加起来就是了；如果某个联通分量没有入度为0 的点，那么就加1.
task B要求把这些联通分量连接成一个连通图，最简单的办法是把这些联通分量连成环。
假第i个联通分量出度为0的点有out个，第i+1个联通分量入度为0的点有in个，那么最少需要max（out，in）个遍才能把他们连接起来。
由于要求最少的遍，那么当out和in最接近的时候，能节省很多边，
考虑这个例子（in,out):(1,2)，（1,1),(2,1);如果这样按顺序连接起来的话，需要2+1+2+1条边，但如果2和3颠倒一下顺序，则需要1+2+1+1条边
因此，每次选取还未匹配的分量 出度最大的一个分量和入度最大的另一个分量，连接起来。
这题好麻烦，很多需要注意的问题。
这题是用java写的，运行速度比c++慢多了
Executing...
Test 1: TEST OK [0.090 secs, 254972 KB]
Test 2: TEST OK [0.090 secs, 254972 KB]
Test 3: TEST OK [0.108 secs, 254972 KB]
Test 4: TEST OK [0.126 secs, 254972 KB]
Test 5: TEST OK [0.126 secs, 254972 KB]
Test 6: TEST OK [0.126 secs, 255384 KB]
Test 7: TEST OK [0.144 secs, 255248 KB]
Test 8: TEST OK [0.162 secs, 255420 KB]
Test 9: TEST OK [0.270 secs, 255792 KB]
Test 10: TEST OK [0.144 secs, 255556 KB]
Test 11: TEST OK [0.162 secs, 255240 KB]
]-----------------------------------------------------------------------------------
/*
ID:yunleis3
PROG:schlnet
LANG:JAVA
*/
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
public class schlnet {
private static final ArrayList<Integer> outdgree0 = null;
static ArrayList<Integer>[] list;
static ArrayList<Integer>[] reverse_list;
static int current_cpnt=0;
static int []dfs_nmbr;
static int []cpnt_nmbr;
static int []dfs_high;
static int dfs_n;
static LinkedList<Integer> dfs_stack=new LinkedList<Integer>();
public static void main(String [] arg) throws IOException{
File file=new File("schlnet.in");
long begin=System.currentTimeMillis();
Scanner scan=new Scanner(file);
FileWriter w=new FileWriter(new File("schlnet.out"));
int total =scan.nextInt();
list=new ArrayList [total+1];
reverse_list=new ArrayList [total+1];
int out=0;
int in=0;
int[] indegree=new int [total+1];
for(int i=1;i<total+1;i++){reverse_list[i]=new ArrayList<Integer>();}
for(int i=1;i<total+1;i++){
list[i]=new ArrayList<Integer>();
while(true){
int t=scan.nextInt();
if(t==0) break;
list[i].add(t);
//indegree[t]++;
reverse_list[t].add(i);
}
if(list[i].size()==0) out++;
}
dfs_nmbr=new int[total+1];
cpnt_nmbr=new int[total+1];
dfs_high=new int[total+1];
dfs_n=total+1;
for(int i=1;i<=total;++i){
if(dfs_nmbr[i]==0)
scc(i);
}
ArrayList<Integer>[] list1=new ArrayList[current_cpnt+1];
ArrayList<Integer>[] reverse_list1=new ArrayList[current_cpnt+1];
for(int i=1;i<current_cpnt+1;++i){
list1[i]=new ArrayList<Integer>();
reverse_list1[i]=new ArrayList<Integer>();
}
for(int i=1;i<=total;i++){
int first=cpnt_nmbr[i];
for(int j=0;j<list[i].size();++j){
int next=cpnt_nmbr[list[i].get(j)];
if(next==first)
continue;
boolean flag=false;
for(int s=0;s<list1[first].size();++s){
if(list1[first].get(s)==next)
{
flag=true;
break;
}
}
if(!flag)
{
list1[first].add(next);
reverse_list1[next].add(first);
indegree[next]++;
}
}
}
list=list1;
reverse_list=reverse_list1;
total=current_cpnt;
for(int i=1;i<=total;i++){
if(indegree[i]==0) in++;
}
boolean[] visited=new boolean[total+1];
int [] componentnum=new int[total+1];
for(int i=0;i<total+1;++i)
{
visited[i]=false;
componentnum[i]=-1;
componentnum[i]=-1;
}
LinkedList<Integer> stack=new LinkedList<Integer>();
int cpnt_g=0;
ArrayList<Integer> indgrees0=new ArrayList<Integer>();
ArrayList<Integer> outdgrees0=new ArrayList<Integer>();
while(true){
boolean find0indgree=false;
int root=0;
boolean finished=true;
ArrayList<Integer> nums=new ArrayList<Integer>();
for(int i=1;i<total+1;++i){
if(!visited[i]&&indegree[i]==0){
root=i;
find0indgree=true;
}
if(!visited[i])
finished=false;
}
if(finished)
break;
if(!find0indgree){
for(int i=1;i<total+1;++i)
if(!visited[i])
root=i;
}
stack.addFirst(root);
visited[root]=true;
int cmpnt_l=cpnt_g++;
nums.add(root);
componentnum[root]=cmpnt_l;
while(!stack.isEmpty()){
int r=stack.removeFirst();
for(int i=0,size=list[r].size();i<size;++i){
int next=list[r].get(i);
if(!visited[next])
{
visited[next]=true;
stack.addFirst(next);
componentnum[next]=cmpnt_l;
nums.add(next);
}
}
for(int i=0,size=reverse_list[r].size();i<size;++i){
int next=reverse_list[r].get(i);
if(!visited[next])
{
visited[next]=true;
stack.addFirst(next);
componentnum[next]=cmpnt_l;
nums.add(next);
}
}
}
int ins0=0,outs0=0;
for(int i=0;i<nums.size();++i){
if(indegree[nums.get(i)]==0)
++ins0;
if(list[nums.get(i)].size()==0)
++outs0;
}
indgrees0.add(ins0);
outdgrees0.add(outs0);
}
int taska=0,taskb=0;
if(total==1){
taska=1;
taskb=0;
}
else if(cpnt_g==1&&indgrees0.get(0)==0&&outdgrees0.get(0)==0){
taska=1;
taskb=0;
}else if(cpnt_g==1){
taska=indgrees0.get(0);
if(taska==0)
taska=1;
taskb=indgrees0.get(0)>outdgrees0.get(0)?indgrees0.get(0):outdgrees0.get(0);
}
else{
in=0;out=0;
boolean[] outvisited=new boolean[cpnt_g];
boolean[] invisited=new boolean[cpnt_g];
for(int i=0;i<cpnt_g;++i){
//pick the max out;
int ptr=-1;
for(int j=0;j<cpnt_g;++j){
if(!outvisited[j]&&(ptr==-1||outdgrees0.get(ptr)>outdgrees0.get(ptr)))
ptr=j;
}
int ptrin=-1;
for(int j=0;j<cpnt_g;++j){
if(!invisited[j]&&(ptrin==-1||indgrees0.get(ptrin)>indgrees0.get(ptrin)))
ptrin=j;
}
outvisited[ptr]=true;
invisited[ptrin]=true;
in=indgrees0.get(ptrin);
out=outdgrees0.get(ptr);
if(in==0)
in=1;
if(out==0)
out=1;
taska+=in;
taskb+=max(out,in);
}
// for(int i=0;i<cpnt_g;++i){
// int next=(i+1)%cpnt_g;
// out=outdgrees0.get(i);
// if(out==0)
// out=1;
// in=indgrees0.get(next);
// if(in==0)
// in=1;
// taska+=in;
// taskb+=max(out,in);
// }
}
FileWriter wr=new FileWriter(new File("schlnet.out"));
wr.write(taska+"\n"+taskb+"\n");
wr.flush();
wr.close();
System.out.print(taska+"\n"+taskb+"\n");
}
static void scc(int v){
dfs_nmbr[v]=dfs_n--;
dfs_stack.addFirst(v);
dfs_high[v]=dfs_nmbr[v];
for(int i=0;i<list[v].size();++i){
int w=list[v].get(i);
if(dfs_nmbr[w]==0){
scc(w);
dfs_high[v]=dfs_high[v]>dfs_high[w]?dfs_high[v]:dfs_high[w];
}
else
if(dfs_nmbr[w]>dfs_nmbr[v]&&cpnt_nmbr[w]==0)
dfs_high[v]=max(dfs_high[v],dfs_nmbr[w]);
}
if(dfs_high[v]==dfs_nmbr[v]){
++current_cpnt;
while(!dfs_stack.isEmpty()){
int x=dfs_stack.removeFirst();
cpnt_nmbr[x]=current_cpnt;
if(x==v){
break;
}
}
}
}
static int max(int x,int y){
return x>y?x:y;
}
}
