hdu 5154 拓扑排序

例题:hdu 5154  链接  http://acm.hdu.edu.cn/showproblem.php?pid=5154

题目意思是第一行先给出n和m表示有n件事,m个关系,接下来输入m行,每行有a,b两个数,他们之间的关系就是第a件事要在

第b件事之前做完,然后问你可不可以在符合这m个关系的情况下把这n件事情做完,可以就输出YES,否则输出NO。

现在先假设a b之间的关系用a指向b来表示,即a-->b。

题目里给的两个样例有点简单,来个稍微复杂一点的好吧。

第一次搞这个,不太会,见谅。看上面这个图,然后我们可以先得到这些数据:

6 7

1 5

1 3

2 5

3 4

3 5

3 6

5 6

入度:就理解为一个点被箭头指的次数(作为终点的次数),上图中 点1的入度为0,点5的入度为3,点3的入度为1。

出度:反一下,箭头出去的次数(作为起点的次数),点1的出度为2,点5的为1。(出度在这题用不到)

我们程序就是先找到入度为0(一开始有点1和点2)的点,然后把这个点标记为走过,再把以这个点为起点的边删掉,

我们先选点1,然后就下面酱紫了。

然后入度为0的点就有点2和点3了,随便选择一个,假设3好吧,然后:

一直这样下去

然后就没有然后了,把点4删了就完了。

以上是符合条件输出YES的情况,假设图是这样的

 那么1和3就构成了一个环,入度为0的点只有2,然后删去2和以2位起点的边:


然后就没有入度为0的边了,然后程序结束,可是所有的点还没有走完(没有做完所有的事情),输出NO。

接下来就是怎么写的问题了。看代码吧

用vector的:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int>v[105];
int n,m,k,t;
int num[105],vis[105];//num数组记录入度数目,vis数组看这个点是否访问过 
void init()
{
    for(int i=1;i<=n;i++)
    v[i].clear();
    memset(num,0,sizeof(num));
    memset(vis,0,sizeof(vis));        
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            num[b]++; //点b入度 +1 
            v[a].push_back(b);//a-->b 
        }
        int flag=0;
        for(int i=1;i<=n;i++)//最多n次循环 
        {
            for(int j=1;j<=n;j++)//找1到n入度为0的点 
            {
                if(vis[j])
                continue;
                if(num[j]==0)
                {
                    vis[j]=1;//标记这个点走过 
                    for(int k=0;k<v[j].size();k++)
                    {
                        if(num[v[j][k]])
                        num[v[j][k]]--;//删边 
                    }
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])//看是不是所有事都做完了 
            flag=1;
        }
        if(flag)
        printf("NO
");
        else
        printf("YES
");
    }
    return 0;
 } 

再用队列和链式前向星优化一下:

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,k,t;
struct node{
    int v,next;
}str[10005];
int head[105],vis[105],in[105],cnt;
queue<int>q;
void add(int u,int v)
{
    str[++cnt].v=v;
    str[cnt].next=head[u];
    head[u]=cnt;
}
void init()
{
    memset(vis,0,sizeof(vis));
    memset(head,-1,sizeof(head));
    memset(in,0,sizeof(in));
    cnt=0;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);
            in[b]++;
        }
        while(!q.empty())
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(!in[i])
            q.push(i);
        }
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            vis[u]=1;
            for(int i=head[u];i!=-1;i=str[i].next)
            {
                int v=str[i].v;
                if(in[v])
                in[v]--;
                if(in[v]==0&&!vis[v])
                q.push(v);
            }
        }
        int flag=1;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                flag=0;
                break;
            }
        }
        if(flag)
        printf("YES
");
        else
        printf("NO
");
    }
    return 0;
}
原文地址:https://www.cnblogs.com/6262369sss/p/8836250.html