[poj1236]Network of Schools(targin缩点SCC)

题意：有N个学校，从每个学校都能从一个单向网络到另外一个学校。
1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。
2：至少需要添加几条边，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。

解题关键：1、缩点之后求出入度为0的点的个数；

　　　　　2、缩点之后入度为0点和出度为0点的个数的max，(因为是任意点可到达全图),若存在点到达全图，添加入度-1条边即可。

注意特判只有一个节点的情况。

dfn需要初始化

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 #define MAXN 120

 #define MAXM 100010

 struct edge{

     int to,nxt;

 }e[MAXM];

 int degree1[MAXN],degree2[MAXN];

 int head[MAXN],st[MAXN],dfn[MAXN],lowest[MAXN],belong[MAXN];

 bool inst[MAXN];

 int n,scnt,top,tot;//scnt从1开始

 void init(){

     memset(head,-,sizeof head);

     memset(degree1,,sizeof degree1);

     memset(degree2,,sizeof degree2);

     scnt=top=tot=;

 }

 void add_edge(int u, int v){

     e[tot].to=v;

     e[tot].nxt=head[u];

     head[u]=tot++;

 }

 void Tarjan(int u){

     dfn[u]=lowest[u]=++tot;

     inst[u]=;

     st[top++]=u;

     for(int i=head[u];i!=-;i=e[i].nxt){

         int v=e[i].to;

         if(!dfn[v]){

             Tarjan(v);

             lowest[u]=min(lowest[u],lowest[v]);

         }

         else if(inst[v]){

             lowest[u]=min(lowest[u],dfn[v]);//也可用lowest

         }

     }

     if(dfn[u]==lowest[u]){

         scnt++;

         int t;

         do{

             t=st[--top];

             inst[t]=false;

             belong[t]=scnt;

         }while(t!=u);

     }

 }

 void solve(){//缩点

     for(int i=;i<=n;i++)  if(!dfn[i])  Tarjan(i);

     for(int i=;i<=n;i++){

         for(int j=head[i];j!=-;j=e[j].nxt){

             if(belong[i]!=belong[e[j].to]){

                 degree1[belong[i]]++,degree2[belong[e[j].to]]++;

             }

         }

     }

     int sum1=,sum2=;

     for(int i=;i<=scnt;i++){

         if(!degree1[i]) sum1++;

         if(!degree2[i]) sum2++;

     }

     if(scnt==){//1个节点进行特判

         printf("1\n0\n");

         return;

     }

     printf("%d\n",sum2);

     printf("%d\n",max(sum1,sum2));

     return;

 }

 int main(){

     int a;

     while(scanf("%d",&n)!=EOF){

         init();

         int m=;

         while(scanf("%d",&a)){

             if(a==){

                 m++;

                 if(m>n) break;

                 continue;

             }

             add_edge(m,a);

         }

         solve();

     }

     return ;

 }

巴特西

[poj1236]Network of Schools(targin缩点SCC)

最新文章

热门文章