HDU3836 Equivalent Sets 强联通分量 Tarjan - c++编程基础

因为团队合作的原因，我主要是要学好数论补枪数据结构还有多多做DP这类题目，图论很差劲，感觉学图论真的要听大神的话，好好看书，静下心来好好的看，看完一遍可能什么都不懂，但是对各个名字理解了，结合做题，很快就会明白很多，图论比较抽象的建图，一定要多多在脑海中构造，看书很重要，这个是本菜鸟的建议，多多包涵，题目看上去复杂，题目也比较短，耐心读一读，仔细分析一下所谓的子集和集合的关系什么的，乱七八糟理清楚就可以了，这里不解释了，弄清楚以后你会发现其实就是求强连通分量而已，一开始没有注意n < 1的情况，导致WA了，

#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 * 10]; int head[20000 + 10],low[20000 + 10],dfn[20000 + 10],id[20000 + 10],Stack[20000 + 10]; bool vis[20000 + 10]; int vis_num,stack_num,scc_num,tot; void clear() { memset(head,-1,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,-1,sizeof(dfn)); memset(id,0,sizeof(id)); memset(Stack,0,sizeof(Stack)); memset(vis,false,sizeof(vis)); vis_num = 0; stack_num = 0; scc_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 main() { int n,m; while(scanf("%d %d",&n,&m) == 2) { clear(); while(m--) { int a,b; scanf("%d %d",&a,&b); addedge(a,b); } cal(n); if(scc_num == 1 || n < 1)//注意了 { puts("0"); continue; } int in[20000 + 10],out[20000 + 10]; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(int i=0;i