POJ 1236 Network of Schools（tarjan）题解-白红宇

POJ 1236 Network of Schools（tarjan）题解

阅读量：4967 次

发布时间：2019-06-12

本文共 620 字，大约阅读时间需要 2 分钟。

题意：一个有向图。第一问：最少给几个点信息能让所有点都收到信息。第二问：最少加几个边能实现在任意点放信息就能传遍所有点

思路：把所有强连通分量缩成一点，然后判断各个点的入度和出度

tarjan算法：

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
              #include
             
              #include
              
               #include
               
                #include
                
                 #define INF 0x3f3f3f3fconst int N=110;const int MOD=1000; using namespace std;int n,index,scc_cnt; //scc_cnt记录SCC int dfn[N],low[N],sccno[N],in[N],out[N];vector
                 
                   g[N];stack
                  
                    s;void tarjan(int x){ int i; dfn[x]=low[x]=++index; s.push(x); for(i=0;i