POJ2762 Going from u to v or from v to u? 强连通 Tarjan缩点+拓扑排序topsort - c++编程基础

过题率并不高，肯定有什么陷阱的，所以仔细读了题目，有个地方还是要注意的，检验一个图中任意两点A跟B是否可以到达，即 A->B或者B-> A 或者A<-->B，所以这个不是一个简简单单的强联通分量的问题了，要先进行缩点操作，此时若此图要满足题目的要求的话，化简过后的图肯定是符合topsort的性质的，因为要任意两点可以到达（注意不要求互相到达）,所以可以用topsort来解决，在sort过程中出现超过一个以上的入度为0的点的话，那么此图就不符合题目要求了

#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[1000 * 10],edge2[1000 * 10]; int head[1000 + 10],low[1000 + 10],dfn[1000 + 10],id[1000 + 10],Stack[1000 + 10],out[1000 + 10]; bool vis[1000 + 10]; int vis_num,scc_num,tot,stack_num,tot2; void clear() { memset(head,-1,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,-1,sizeof(dfn)); memset(Stack,0,sizeof(Stack)); memset(vis,false,sizeof(vis)); memset(id,0,sizeof(id)); memset(out,0,sizeof(out)); vis_num = 0; scc_num = 0; tot = 0; stack_num = 0; tot2 = 0; } void addedge(int u,int v) { edge[tot].from = u; edge[tot].to = v; edge[tot].nex = head[u]; head[u] = tot++; } void Addedge(int u,int v) {//缩点后再次加边 edge2[tot2].from = u; edge2[tot2].to = v; edge2[tot2].nex = head[u]; head[u] = tot2++; } 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(dfn[u],low[v]); } 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); } bool topsort() { int ans = 0; int mark; for(int i=1;i<=scc_num;i++) { if(out[i] == 0) { mark = i; ans++; } } if(ans > 1)return false; int tmp = scc_num; while(tmp--) { ans = 0; for(int i=head[mark];i!=-1;i=edge2[i].nex) { int u =edge2[i].to; out[u]--; if(out[u] == 0) { ans++; mark = u; } } if(ans > 1)return false; } return true; } int main() { int n,m; int t; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&m); clear(); while(m--) { int a,b; scanf("%d %d",&a,&b); addedge(a,b); } cal(n); memset(head,-1,sizeof(head)); for(int i=0;i