概念：

　　一个有向无环图的拓扑序列是将图中的顶点排成一个线性序列，使得对于图中任意一对顶点u，v。若存在边<u,v>，则线性序列中u出现在v之前。

算法实现：

（1）若图中的点入度均大于0则不存在拓扑序列，否则进行第二步

（2）取一个入度为0的点u并将其放置序列末尾

（3）删除点u以及从u伸出的边，即将与u相连的点的入度减1

（4）若图中还存在顶点，再从（1）开始

最基础的模板：

#include <bits/stdc++.h>
using namespace std;
vector<int> v[1010];
queue<int> q;
int ans[1010];
int n,m;
void tuopu()
{
    int cnt = 0;
    while(!q.empty())
        q.pop();
    for(int i=1;i<=n;i++)
        if(in[i] == 0)
            q.push_back(i);
    while(!q.empty())
    {
        int k = q.front();
        ans[++cnt] = k;
        q.pop();
        for(int i=0;i<v[k].size();i++)
        {
            in[ v[k][i] ]--;
            if(in[ v[k][i] ] == 0)
                q.push_back(v[k][i]);
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        cout<<ans[i]<<" ";
    }
    return ;
}
int main()
{
    while(cin>>n>>m &&n)
    {
        for(int i=1;i<=n;i++)
            v[i].clear();
        memset(in,0,sizeof(in));
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            v[x].push_back(y);
            in[y]++;
        }
        tuopu();
    }
   
    return 0;
}

定向题目：

1.有向图判环 HDU - 3342

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[110];
queue<int> q;
int in[110];
int n,m,x,y;
bool tuopu()
{
    int cnt = 0;
    while(!q.empty())
        q.pop();
    for(int i=0;i<n;i++)
        if(in[i] == 0){
            q.push(i);
            cnt++;
        }

    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(int i=0;i<v[k].size();i++)
        {
            in[ v[k][i] ]--;
            if(in[ v[k][i] ] == 0){
                q.push(v[k][i]);
                cnt++;
            }

        }
    }
    if(cnt != n)
        return false;
    return true;
}
int main()
{
    while(cin>>n>>m &&n)
    {
        for(int i=0;i<n;i++)
            v[i].clear();
        memset(in,0,sizeof(in));
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            v[x].push_back(y);
            in[y]++;
        }
        if(tuopu()){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }

    return 0;
}

2. 反向拓扑深搜 HDU - 2647

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
ll money = 0;
vector<int> v[10010];
queue<int> q;
int in[10010];
int ans[10010];
int n,m,x,y;
void tuopu()
{
    int cnt = 0;
    while(!q.empty())
        q.pop();
    for(int i=1;i<=n;i++)
        if(in[i] == 0){
            q.push(i);
        }

    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        cnt++;
        for(int i=0;i<v[k].size();i++)
        {
            in[ v[k][i] ]--;
            if(in[ v[k][i] ] == 0){
                q.push(v[k][i]);
                ans[v[k][i]] = max(ans[k]+1,ans[v[k][i]]);
            }
        }
    }
    if(cnt == n)
    {
        money = 888*n;
        for(int i=1;i<=n;i++)
        {
            money += ans[i];
        }
        cout<<money<<endl;
    }else{
        cout<<"-1"<<endl;
    }
    return ;
}
int main()
{
    while(cin>>n>>m && n)
    {
        for(int i=1;i<=n;i++)
            v[i].clear();
        memset(in,0,sizeof(in));
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            v[y].push_back(x);
            in[x]++;
        }
        tuopu();
    }

    return 0;
}

3.正反拓扑和 dfs ZOJ - 4124

#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n,m,k1,k2;
vector<int> v1[110];
vector<int> v2[110];
queue<int> q;
int sign[110];
int in1[110];

bool tuopu()
{
    while(!q.empty())
        q.pop();
    int cnt = 0;
    for(int i=1;i<=n;i++)
        if(in1[i] == 0)
            q.push(i);
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        cnt++;
        in1[k] = -1;
        for(int i=0;i<v1[k].size();i++)
        {
            in1[ v1[k][i] ]--;
            if(in1[ v1[k][i] ] == 0)
                q.push(v1[k][i]);
        }
    }
    if(cnt != n)
        return false;
    return true;
}

void dfs1(int x)
{
    sign[x] = 1;
    for(int i=0;i<v1[x].size();i++)
    {
        if(!sign[v1[x][i]]){
            k1++;
            dfs1(v1[x][i]);
        }
    }
    return ;
}
void dfs2(int x)
{
    sign[x] = 1;
    for(int i=0;i<v2[x].size();i++)
    {
        if(!sign[v2[x][i]]){
            k2++;
            dfs2(v2[x][i]);
        }
    }
    return ;
}
int main()
{
    int t,x,y;
    cin>>t;
    while(t--)
    {
        for(int i=1;i<=n;i++){
            v1[i].clear();
            v2[i].clear();
        }
        memset(in1,0,sizeof(in1));

        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            v1[x].push_back(y);
            v2[y].push_back(x);
            in1[y]++;
        }
        if(tuopu())
        {
            for(int i=1;i<=n;i++)
            {
                k1 = k2 = 0;
                memset(sign,0,sizeof(sign));
                dfs1(i);
                memset(sign,0,sizeof(sign));
                dfs2(i);
                if(k1 <= (n-1)/2 && k2 <= (n-1)/2)
                    cout<<"1";
                else
                    cout<<"0";
            }
            cout<<endl;
        }else{
            for(int i=1;i<=n;i++)
                cout<<"0";
            cout<<endl;
        }
    }
    return 0;
}

深度理解拓扑排序

全站热榜