hdu3342-判断有向图中是否存在(至少)3元环或回路-拓扑排序

题目大意：

给你一个关系图，判断是否合法。每个人都有师父和徒弟，可以有很多个；

若A是B的师父，B是C的师父，则A也算C的师父。

不合法：

1) . 互为师徒；(有回路)
2) .你的师父是你徒弟的徒弟，或者说你的徒弟是你师父的师父。(出现回路)

思路：

判断有向图中是否存在回路或至少3元环；
此题至少有三种做法，此处更新拓扑排序的做法：

解题方法：

一：拓扑排序：

1) . 统计每个点的入度；

2) . 将入度为0的点加入队列；

3) . 出去队首元素，将此元素所连接的点入度减一，若此后入度为0则加入队列；

4) . 判断队列循环次数，若等于n则不存在3元环，则此关系图合法；

题目链接：

点击打开链接

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<map>

#include<stack>

#include<vector>

#include<ctime>

using namespace std;

const int  N = ;

const int  M = ;

int n,m;

int tot,flag;

int in[N],head[N];

struct lp

{

    int u,v,nex;

    lp(){}

    lp(int a,int b,int c):

    u(a),v(b),nex(c){}

}cw[N];

void add(int a,int b){

    cw[++tot]=lp(a,b,head[a]);

    head[a]=tot;

}

void tuopu(){

    queue<int>Q;

    while(!Q.empty())Q.pop();

    for(int i=;i<n;++i){

        if(in[i]==)Q.push(i);

    }

    int t=;

    while(!Q.empty()){

        t++;

        int u=Q.front();Q.pop();

        for(int i=head[u];i!=-;i=cw[i].nex){

            int v=cw[i].v;

            in[v]--;

            if(in[v]==)Q.push(v);

        }

    }

    if(t==n)flag=;

}

int main(int argc, char const *argv[])

{

    int a,b;

    while(~scanf("%d%d",&n,&m)&&(n)){

        memset(in,,sizeof(in));

        tot=-;

        memset(head,-,sizeof(head));

        for(int i=;i<m;++i){

            scanf("%d%d",&a,&b);

            add(a,b);

            in[b]++;

        }

        flag=;

        tuopu();

        if(flag)printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

二：Tarjan：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<map>

#include<stack>

#include<vector>

#include<ctime>

using namespace std;

const int  N = ;

const int  M = ;

int n,tot,flag,idex;

int head[N],vis[N];

int low[N],dfn[N];

int qltNum;

int qltMap[N];

stack<int>st;

struct lp{

    int to,nex;

    lp(){}//构造函数

    lp(int a,int b):

    to(a),nex(b){}

}cw[N*N];

void add(int a,int b){

    cw[++tot]=lp(b,head[a]);

    head[a]=tot;

}

void dfs(int u,int fa){

    dfn[u]=low[u]=++idex;

    vis[u]=;

    st.push(u);

    int v;

    for(int i=head[u];i!=-;i=cw[i].nex){

        v=cw[i].to;

        if(v==fa){

            flag=;

            break;

        }

        if(!vis[v]){

            dfs(v,u);

            if(flag)return;

            low[u]=min(low[u],low[v]);

        }else if(vis[v]==){

            low[u]=min(low[u],dfn[v]);

        }

    }

    if(low[u]==dfn[u]){//缩点

        qltNum++;

        int t=;

        do{

            t++;

            v=st.top();st.pop();

            vis[v]=;

            qltMap[v]=qltNum;

            if(t>=){

                flag=;

                return;

            }

        }while(v!=u);

        //cout<<t<<"\n";

    }

}

void tarjan(){

    for(int i=;i<=n;++i){

        if(!vis[i]){

            dfs(i,-);

        }

        if(flag)return;

    }

}

void init(){//初始化

    while(!st.empty())st.pop();

    qltNum=idex=flag=;

    tot=-;

    memset(head,-,sizeof(head));

    memset(vis,,sizeof(vis));

    memset(qltMap,,sizeof(qltMap));

}

int main(int argc, char const *argv[]){

    int a,b,m;

    while(~scanf("%d%d",&n,&m)&&(n)){

        init();

        memset(head,-,sizeof(head));

        for(int i=;i<m;++i){

            scanf("%d%d",&a,&b);

            a++,b++;

            add(a,b);

        }

        tarjan();

        if(flag)printf("NO\n");

        else printf("YES\n");

    }

    return ;

}

巴特西

hdu3342-判断有向图中是否存在(至少)3元环或回路-拓扑排序

最新文章

热门文章