程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj-2762-Going from u to v or from v to u?-tarjan算法求縮點+算是不是一字鏈

poj-2762-Going from u to v or from v to u?-tarjan算法求縮點+算是不是一字鏈

編輯:C++入門知識

tarjan求縮點,然後算縮點之後的圖是不是一字鏈。

判斷是不是一字鏈很簡單,直接dfs求出一條最長邊。

看最長邊是不是等於縮點之後的數目即可。

#include 
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define maxm 10000
#define maxn 1100
#define eps 0.000001
#define zero(x) ((fabs(x)qq;
    void init()
    {
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(shuyu,0,sizeof(shuyu));
        memset(dnf,0,sizeof(dnf));
        memset(low,0,sizeof(low));
        memset(instack,0,sizeof(instack));
        memset(viss,0,sizeof(viss));
        while(!qq.empty())qq.pop();
        num=0;
        nums=1;
        times=1;
    }
    void add(int u,int v)
    {
        edge[num].u=u;
        edge[num].v=v;
        edge[num].next=head[u];
        head[u]=num++;
    }
    void tarjan(int x)
    {
        dnf[x]=low[x]=times++;
        instack[x]=1;
        qq.push(x);
        for(int i=head[x]; i!=-1; i=edge[i].next)
        {
            int y=edge[i].v;
            if(!dnf[y])
            {
                tarjan(y);
                low[x]=min(low[x],low[y]);
            }
            else if(instack[y])
            {
                low[x]=min(low[x],dnf[y]);
            }
        }
        if(low[x]==dnf[x])
        {
            int y=-1;
            while(x!=y)
            {
                y=qq.top();
                shuyu[y]=nums;
                qq.pop();
                instack[y]=0;
            }
            nums++;
        }
    }
    void start()
    {
        for(int i=1; i<=n; i++)
        {
            if(!dnf[i])tarjan(i);
        }
    }
    int dfs(int x,int p)
    {
        int mm=p;
        for(int i=head[x]; i!=-1; i=edge[i].next)
        {
            mm=max(mm,dfs(edge[i].v,p+1));
        }
        return mm;
    }
} G,g;
int main()
{
    int n,i,j,m,a,b,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        G.init();
        g.init();
        G.n=n;
        for(i=1; i<=m; i++)
        {
            scanf("%d%d",&a,&b);
            G.add(a,b);
        }
        G.start();
        g.n=G.nums;
        int nin,nout;
        nin=nout=0;
        for(i=1; i<=G.n; i++)
        {
            for(j=G.head[i]; j!=-1; j=G.edge[j].next)
            {
                int u=G.edge[j].u;
                int v=G.edge[j].v;
                if(G.shuyu[u]==G.shuyu[v])continue;
                G.id[G.shuyu[v]]++;
                G.od[G.shuyu[u]]++;
               // cout<1||nout>1)
        {
            cout<<"No"<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved