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];stacksta;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;i1)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();
        vectormy;
      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;
    stackmys;
    for(int i=0;imy;
      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;
}