hdu 1811 ufset综合

?

题意：给一个图，要求是没有环，并且能从一点出发一笔画完所有点。定性判断出来。

想恢复一下算法，判断矛盾用的强连通性的tarjan,不能确定用的模拟。

?

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; int fa[30105]; int n,m; int ind[30028]; int find(int x) { if(x==fa[x])return x; fa[x]=find(fa[x]); return fa[x]; } int e[100154][3];int head[30023];int nume; void inline adde(int i,int j) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume++; } struct zz { int x,y; char t; }; int ins[20009];stack
       
        sta;int low[20025];int dfn[20025]; int times;int vis[20025];int scc[20251];int numb=0; void tarjan(int u) { dfn[u]=low[u]=times++; ins[u]=1; sta.push(u); for(int j=head[u];j!=-1;j=e[j][1]) { int v=e[j][0]; if(!vis[v]) { vis[v]=1; tarjan(v); if(low[u]>low[v])low[u]=low[v]; } else if(ins[v]) { if(dfn[v]
        
         temp; for(int i=0;i
         
          1)return 2; numv--; } return 0; } void init() { for(int i=0;i<10005;i++) { fa[i]=i; head[i]=-1; low[i]=dfn[i]=0; scc[i]=vis[i]=ins[i]=ind[i]=0; } numb=times=nume=0; } int main() { while(~scanf(%d%d,&n,&m)) { int marks=0; int aa,bb;char temp; init(); vector
          
           my; for(int i=0;i
           
            >aa>>temp>>bb; if(temp=='=') { int xx=find(aa); int yy=find(bb); if(xx!=yy)fa[xx]=yy; } else { zz cur; cur.x=aa;cur.y=bb;cur.t=temp; my.push_back(cur); } } for(int i=0;i
            
             
?
             
传统方法： ufset拓扑：
             
?
             
#include
              
               
#include
               
                 #include
                
                  #include
                 
                   #include
                  
                    using namespace std; const int maxn=100004; int fa[maxn]; int n,m; int ind[maxn]; int sums=0; vector
                   
                     >e(maxn); int find(int x) { if(x==fa[x])return x; fa[x]=find(fa[x]); return fa[x]; } struct zz { int x,y; char t; }; int judge() { int ans=0; stack
                    
                     mys; for(int i=0;i
                     
                      my; for(int i=0;i
                      
                       >aa>>temp>>bb; if(temp=='=') { int xx=find(aa); int yy=find(bb); if(xx!=yy){fa[xx]=yy;sums--;} } else { zz cur; cur.x=aa;cur.y=bb;cur.t=temp; my.push_back(cur); } } for(int i=0;i
                       
                        ') { int xx=find(my[i].x); int yy=find(my[i].y); e[xx].push_back(yy); ind[yy]++; } } int ans=judge(); if(n==0) ans=0; if(ans==2) printf(UNCERTAIN ); else if(ans==1) printf(CONFLICT ); else printf(OK ); } return 0; } 
                       
                      
                     
                    
                   
                  
                 
                
               
              
 
             
 
             
 
             
?
 
             
?