# 5.3.3 Network of Schools 校园网

5.3.3 Network of Schools 校园网

``````5
2 4 3 0
4 5 0
0
0
1 0``````

``````1
2``````

``````#include <iostream>
#include <cstring>
using namespace std;

#define MAXN 110

typedef struct edge
{
int t;
struct edge *next;
}edge;

int DFN[MAXN],LOW[MAXN];
bool instack[MAXN];
int Belong[MAXN];
int Stap[MAXN];
int Stop,Bcnt,Dindex;
edge* V[MAXN];
int n;
int res;
int indegree[MAXN],outdegree[MAXN];
int idcnt,odcnt;

void tarjan(int i)
{
int j;
DFN[i]=LOW[i]=++Dindex;
instack[i]=true;
Stap[++Stop]=i;
for(edge *e=V[i];e;e=e->next)
{
j=e->t;
if(!DFN[j])
{
tarjan(j);
if(LOW[j]<LOW[i])
LOW[i]=LOW[j];
}
else if(instack[j]&&DFN[j]<LOW[i])
LOW[i]=DFN[j];
}
if(DFN[i]==LOW[i])
{
Bcnt++;
do
{
j=Stap[Stop--];
instack[j]=false;
Belong[j]=Bcnt;
}while(j!=i);
}
}

void solve()
{
int i;
Stop=Bcnt=Dindex=0;
memset(DFN,0,sizeof(DFN));
memset(LOW,0,sizeof(LOW));
for(i=1;i<=n;i++)
if(!DFN[i])
tarjan(i);
}

int main()
{
int i;
int tmp;
edge* q=NULL;
edge* p=NULL;
memset(V,0,sizeof(V));
memset(instack,0,sizeof(instack));
cin>>n;
for(i=1;i<=n;i++)
{
while(cin>>tmp)
{
if(tmp==0)
break;
q=new edge;
q->t=tmp;
p=V[i];
if(V[i]==0)
{
V[i]=q;
q->next=NULL;
}
else
{
while(p->next)
p=p->next;
q->next=p->next;
p->next=q;
}
}
}
solve();
memset(indegree,0,sizeof(indegree));
memset(outdegree,0,sizeof(outdegree));
for(i=1;i<=n;i++)
{
for(edge *e=V[i];e;e=e->next)
{
if(Belong[i]!=Belong[e->t])
{
indegree[Belong[i]]++;
outdegree[Belong[e->t]]++;
}
}
}
idcnt=odcnt=0;
if(Bcnt==1)
cout<<"1"<<endl<<"0"<<endl;
else
{
for(i=1;i<=Bcnt;i++)
{
if(indegree[i]==0)
idcnt++;
if(outdegree[i]==0)
odcnt++;
}
cout<<odcnt<<endl;
if(idcnt>odcnt)
cout<<idcnt<<endl;
else
cout<<odcnt<<endl;
}
return 0;
}``````

``````#include<iostream>
#include<cstring>
using namespace std;

int g1[101][101],g2[101][101];
int into[101],out[101],belong[101];
bool vis[101],dis[101][101];
int n,m,I0,O0;

void g1dfs(int k)
{
vis[k]=true;
for (int i=1;i<=g1[k][0];i++)
if (!vis[g1[k][i]])
g1dfs(g1[k][i]);
}
void g2dfs(int k)
{
belong[k]=m;
for (int i=1;i<=g2[k][0];i++)
if (vis[g2[k][i]] && !belong[g2[k][i]])
g2dfs(g2[k][i]);
}
void solve()
{
memset(vis,false,sizeof(vis));
memset(belong,0,sizeof(belong));
m=0;
for (int i=1;i<=n;i++)
if (belong[i]==0)
{
g1dfs(i);
m++;
g2dfs(i);
memset(vis,false,sizeof(vis));
}
memset(dis,false,sizeof(dis));
for (int i=1;i<=n;i++)
for (int j=1;j<=g1[i][0];j++)
dis[belong[i]][belong[g1[i][j]]]=true;
memset(into,0,sizeof(into));
memset(out,0,sizeof(out));
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++)
if (i!=j && dis[i][j])
{
into[j]++;
out[i]++;
}
I0=0;O0=0;
for (int i=1;i<=m;i++)
{
if (into[i]==0) I0++;
if (out[i]==0) O0++;
}
}
void print()
{
if (m==1) printf("1\n0\n");
else
{
printf("%d\n",I0);
if (I0>O0) printf("%d\n",I0);
else printf("%d\n",O0);
}
}
int main()
{
scanf("%d",&n);
memset(g1,0,sizeof(g1));
memset(g2,0,sizeof(g2));
int x;
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
while (x)
{
g1[i][++g1[i][0]]=x;
g2[x][++g2[x][0]]=i;
scanf("%d",&x);
}
}
solve();
print();
return 0;
}``````