HDU2767 Proving Equivalences 强连通 Tarjan 缩点成树统计

题目给了N个点M条边，问还需要几条边可以是的此图变成强连通图，我们知道 A->B,B->C,C->A,这样A,B,C三点成环，如果此时有一个点D与A连接，其实D就与B,C都连接了，所以可以把A,B,C当作一个整体来处理，也就是所谓的缩点，把整个图先缩成一个个团点，只要把这几个团点连在一起实际上所有的点就连在了一起了，缩点完成后，统计一下连通的出度入度，取大的那个就可以了，时间宽裕，统计完全可以暴力一点

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; // typedef struct Node { int from,to; int nex; }; Node edge[20000 * 5]; int dfn[20000 + 10],low[20000 + 10],head[20000 + 10],Stack[20000 + 10],id[20000 + 10]; bool vis[20000 + 10]; int n,m,scc_num,vis_num,stack_num,tot; void clear() { memset(dfn,-1,sizeof(dfn)); memset(low,0,sizeof(low)); memset(head,-1,sizeof(head)); memset(Stack,0,sizeof(Stack)); memset(id,0,sizeof(id)); memset(vis,false,sizeof(vis)); scc_num = 0; vis_num = 0; stack_num = 0; tot = 0; } void addedge(int u,int v) { edge[tot].from = u; edge[tot].to = v; edge[tot].nex = head[u]; head[u] = tot++; } void tarjan(int v) { dfn[v] = low[v] = ++vis_num; vis[v] = true; Stack[stack_num++] = v; for(int i=head[v];i!=-1;i=edge[i].nex) { int u = edge[i].to; if(dfn[u] == -1) { tarjan(u); low[v] = min(low[u],low[v]); } else if(vis[u]) low[v] = min(low[v],dfn[u]); } int tmp; if(low[v] == dfn[v]) { scc_num++; do { tmp = Stack[--stack_num]; id[tmp] = scc_num; vis[tmp] = false; }while(tmp != v); } } void cal(int n) { for(int i=1;i<=n;i++) if(dfn[i] == -1) tarjan(i); } int detal(int n) { if(scc_num <= 1)return 0; int in[20000 + 10],out[20000 + 10]; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(int i=1;i<=n;i++) { int u = id[i]; for(int j=head[i];j!=-1;j=edge[j].nex) { int v = id[edge[j].to]; if(u != v) in[u]++,out[v]++; } } int ans1 = 0; int ans2 = 0; for(int i=1;i<=scc_num;i++) if(!in[i]) ans1++; for(int i=1;i<=scc_num;i++) if(!out[i]) ans2++; return (max(ans1,ans2)); } int main() { int t; scanf("%d",&t); while(t--) { clear(); scanf("%d %d",&n,&m); int a,b; while(m--) { scanf("%d %d",&a,&b); addedge(a,b); } cal(n); int ans = detal(n); printf("%d\n",ans); } return EXIT_SUCCESS; }

HDU2767 Proving Equivalences 强连通 Tarjan 缩点成树 统计