精华内容
下载资源
问答
  • 拓扑排序例题

    2019-06-05 01:40:07
    拓扑排序 以下是例题拓扑排序·一 简单拓扑判环 #include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 7; vector<int> G[maxn]; int inDeg[maxn]; int n,m; queue<int>q; int...

    不懂的看这里

    拓扑排序

    以下是例题:

    拓扑排序·一

    简单拓扑判环

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 7;
    vector<int> G[maxn];
    int inDeg[maxn];
    int n,m;
    queue<int>q;
    int sum;
    bool top(){
    while(!q.empty()) q.pop();
    sum = 0;
    
    
    for(int  i = 1;i <= n ; i++) if(!inDeg[i]) q.push(i);
    while(!q.empty()){
        int to = q.front();
        q.pop();
        sum ++;
        for(int  i = 0; i < G[to].size(); i++){
            int edge = G[to][i];
            inDeg[edge] --;
            if(!inDeg[edge]) q.push(edge);
        }
    
    }
    if(sum == n) return 1;
    else return 0;
    }
    
    
    int main(){
       // int n ;
       int t;
        cin >> t ;
        while(t--){
        cin >> n;
        cin >> m;
        memset(G,0,sizeof(G));
        memset(inDeg,0,sizeof(inDeg));
        for(int i  =1;i <= m ; i++) {
            int u , v;
            cin >> u >> v;
            G[u].push_back(v);
            inDeg[v]++;
        }
        if(top()) cout << "Correct" << endl;
        else cout << "Wrong" << endl;
        }
        return 0;
    
    }
    
    

    Legal or Not

    同上,注意0 ~ n-1

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 7;
    const int mod = 142857;
    vector<int> G[maxn];
    int virus[maxn];
    int inDeg[maxn];
    int n,m;
    int sum = 0;
    queue<int>q;
    
    bool topsort(){
        while(!q.empty()) q.pop();
        sum = 0;
    
    
        for(int  i = 0;i < n ; i++) if(!inDeg[i]) q.push(i);
            while(!q.empty()){
                int to = q.front();
                q.pop();
                sum ++;
                for(int  i = 0; i < G[to].size(); i++){
                    int edge = G[to][i];
                    inDeg[edge] --;
                    if(!inDeg[edge]) q.push(edge);
          //  virus[edge] = (virus[edge] + virus[to]) % mod;
                }
    
            }
            if(sum == n)return 1;
            else return 0;
        }
    
    
        int main(){
       // int n ;
    
            int k ;
    
            while(cin >> n){
                cin >> m;
                if(!n&&!m) break;
       // cin >> k;
        //memset(virus, 0 , sizeof virus);
        //int x;
        //for(int i = 1; i <= k ; i++) cin >> x,virus[x] ++;
                memset(G,0,sizeof(G));
                memset(inDeg,0,sizeof(inDeg));
                for(int i  =1;i <= m ; i++) {
                    int u , v;
                    cin >> u >> v;
                    G[u].push_back(v);
                    inDeg[v]++;
                }
                if(topsort()) 
                    puts("YES");
                else 
        puts("NO");    //int sum = 0;
        //for(int i = 1; i <= n; i++) sum = (sum + virus[i] ) % mod;
        //cout << sum << endl;
    }
    return 0;
    
    }
    

    拓扑排序·二
    拓扑排序的应用

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 7;
    const int mod = 142857;
    vector<int> G[maxn];
    int virus[maxn];
    int inDeg[maxn];
    int n,m;
    queue<int>q;
    
    void topsort(){
    while(!q.empty()) q.pop();
    //sum = 0;
    
    
    for(int  i = 1;i <= n ; i++) if(!inDeg[i]) q.push(i);
    while(!q.empty()){
        int to = q.front();
        q.pop();
        //sum ++;
        for(int  i = 0; i < G[to].size(); i++){
            int edge = G[to][i];
            inDeg[edge] --;
            if(!inDeg[edge]) q.push(edge);
            virus[edge] = (virus[edge] + virus[to]) % mod;
        }
    
    }
    
    }
    
    
    int main(){
       // int n ;
    
        int k ;
    
        while(cin >> n){
        cin >> m;
        cin >> k;
        memset(virus, 0 , sizeof virus);
        int x;
        for(int i = 1; i <= k ; i++) cin >> x,virus[x] ++;
        memset(G,0,sizeof(G));
        memset(inDeg,0,sizeof(inDeg));
        for(int i  =1;i <= m ; i++) {
            int u , v;
            cin >> u >> v;
            G[u].push_back(v);
            inDeg[v]++;
        }
        topsort();
        int sum = 0;
        for(int i = 1; i <= n; i++) sum = (sum + virus[i] ) % mod;
        cout << sum << endl;
        }
        return 0;
    
    }
    
    

    Skiing

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 7;
    int n , m;
    vector<pair<int,int> >G[maxn];
    int inDeg[maxn];
    int dp[maxn];
    void topsort(){
    queue<int>q;
    while(!q.empty())q.pop();
    for(int i = 1; i <= n ; i++) if(!inDeg[i]) q.push(i);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i = 0; i < G[now].size(); i++){
            int to = G[now][i].first;
            inDeg[to]--;
            if(!inDeg[to]) q.push(to);
            dp[to] = max(dp[to],dp[now] + G[now][i].second);
        }
    
    }
    
    }
    
    int main(){
    int t;
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> m;
        memset(inDeg,0,sizeof inDeg);
        memset(dp,0,sizeof dp);
        for(int i = 1;i <= n ; i++) G[i].clear();
        while(m--){
            int u , v, w;
            cin >> u >> v >> w;
            G[u].push_back(make_pair(v,w));
            //G[v].push_back(make_pair((u,w)));
            inDeg[v] ++;
        }
        topsort();
        int maxx = 0;
        for(int i  =1; i <= n ; i++) maxx = max(dp[i],maxx);
        cout << maxx << endl;
    }
    return 0;
    }
    
    

    Almost Acyclic Graph

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 7;
    int n , m;
    int inDeg[maxn],ruDeg[maxn];
    std::vector<int> v[maxn];
    bool topsort(){
    	int sum = 0;
    	queue<int>q;
    	while(!q.empty()) q.pop();
    	for(int i = 1; i <= n ; i++){
    		if(!inDeg[i]) q.push(i);
    	}
    	while(!q.empty()){
    		int now = q.front();
    		q.pop();
    		sum ++;
    		for(int i = 0; i < v[now].size(); i++){
    			int to = v[now][i];
    			if(--inDeg[to] == 0){
    				q.push(to);
    			}
    		}
    	}
    	if(sum == n) return 1;
    	else return 0;
    }
    
    int main(){
    	cin >> n >> m;
    	for(int i  = 1; i <= m ; i++){
    		int u , w;
    		cin >> u >> w;
    		v[u].push_back(w);
    		inDeg[w]++;
    		ruDeg[w]++;
    	}
    	//topsort();
    	if(topsort() == 1){
    		cout << "YES" << "\n" ;
    	}
    	else {
    		bool flag = 0;
    		for(int i = 1; i <= n; i++){
    			memcpy(inDeg,ruDeg,sizeof ruDeg);
    			if(inDeg[i] >= 1){
    				inDeg[i] --;
    				if(topsort() == 1){
    					flag = 1;
    					cout << "YES" << "\n";
    					break;
    				}
    			}
    		}
    		if(!flag) puts("NO");
    	}
    	return 0;
    }
    

    确定比赛名次

    优先队列 + 拓扑(字典序)

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 7;
    int n, m;
    vector<int>G[maxn];
    int inDeg[maxn];
    int dp[maxn];
    int cnt;
    int mp[1000][1000];
    void topsort()
    {
    	priority_queue<int,vector<int>,greater<int> >q;
        //queue<int>q;
        cnt = 0;
        while(!q.empty())q.pop();
        for(int i = 1; i <= n ; i++) if(!inDeg[i]) q.push(i);
        while(!q.empty())
        {
            int now = q.top();
            q.pop();
            dp[cnt++] = now;
            for(int i = 0; i < G[now].size(); i++)
            {
                int to = G[now][i];
                inDeg[to]--;
                if(!inDeg[to]) q.push(to);
            //    dp[to] = max(dp[to],dp[now] + G[now][i].second);
            }
    
        }
    
    }
    
    int main()
    {
        int t;
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
      //  cin >> t;
       
            while(cin >> n >> m){
    		
            memset(inDeg,0,sizeof inDeg);
            memset(dp,0,sizeof dp);
            for(int i = 1; i <= n ; i++) G[i].clear();
            while(m--)
            {
                int u, v, w;
                cin >> u >> v ;
                
                //if(mp[u][v] == 0)
                G[u].push_back(v);
                
                //G[v].push_back(make_pair((u,w)));
                inDeg[v] ++;
            }
            topsort();
            //int maxx = 0;
            for(int i  = 0; i < cnt ; i++)
            printf("%d%c",dp[i]," \n"[i == cnt -1]);
        }
        return 0;
    }
    

    逃生

    举个例子如图:

    在这里插入图片描述

    如果你用优先队列拓扑排序得到的是:3 5 6 4 1 7 8 9 2 0

    但是正确答案为 6 4 1 3 9 2 5 7 8 0 这样使得小的(1)尽量在前面。

    这里我们可以得到 前面的小的不一定排在前面,但是有一点后面大的一定排在后面。

    我们看 6和3不一定3排在前面,因为6后面连了一个更小的数字1能使得6更往前排。

    在看 2和 8,8一定排在后面,因为8后面已经没有东西能使它更往前排(除了0)。

    所以最后我们的做法就是 建立一个反图,跑一边字典序最大的拓扑排序,最后再把这个排序倒过来就是答案了。

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 7;
    int n, m;
    vector<int>G[maxn];
    int inDeg[maxn];
    int dp[maxn];
    int cnt;
    void topsort()
    {
        priority_queue<int> q;
        //queue<int>q;
         cnt = 0;
        while(!q.empty())q.pop();
        for(int i = 1; i <= n ; i++) if(!inDeg[i]) q.push(i);
        while(!q.empty())
        {
            int now = q.top();
            q.pop();
            dp[cnt++] = now;
            for(int i = 0; i < G[now].size(); i++)
            {
                int to = G[now][i];
                inDeg[to]--;
                if(!inDeg[to]) q.push(to);
            //    dp[to] = max(dp[to],dp[now] + G[now][i].second);
            }
    
        }
    
    }
    
    int main()
    {
        int t;
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        cin >> t;
        while(t--)
        {
            cin >> n >> m;
            memset(inDeg,0,sizeof inDeg);
            memset(dp,0,sizeof dp);
            for(int i = 1; i <= n ; i++) G[i].clear();
            while(m--)
            {
                int u, v, w;
                cin >> u >> v ;
                G[v].push_back(u);
                //G[v].push_back(make_pair((u,w)));
                inDeg[u] ++;
            }
            topsort();
            //int maxx = 0;
            for(int i  = cnt - 1; i >= 0 ; i--)
            printf("%d%c",dp[i]," \n"[i == 0]);
        }
        return 0;
    }
    

    Labeling Balls
    优先队列 + 反向拓扑

    //#include<bits/stdc++.h>
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int maxn = 1e5 + 7;
    int n, m;
    vector<int>G[maxn];
    int inDeg[maxn];
    int dp[maxn];
    int cnt;
    int sum ,ans ;
    int mp[1000][1000];
    bool topsort()
    {
    	//queue<int>q;
    	priority_queue<int>q;
        //queue<int>q;
        cnt = 0;
        sum = 0;
        while(!q.empty())q.pop();
        for(int i = 1; i <= n ; i++) if(!inDeg[i]) q.push(i);
        while(!q.empty())
        {
            int now = q.top();
            q.pop();
          //  cout << now << endl;
          sum ++;
            dp[now] = n--;
          //  cout << dp[now] << endl;
            for(int i = 0; i < G[now].size(); i++)
            {
                int to = G[now][i];
                inDeg[to]--;
                if(!inDeg[to]) q.push(to);
            //    dp[to] = max(dp[to],dp[now] + G[now][i].second);
            }
    
        }
    if(sum == ans)return 1;
    else return 0;
    }
    
    int main()
    {
        int t;
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
      //  cin >> t;
         cin >> t;
         while(t--){
    	 
            cin >> n >> m;
    		ans = n;
            memset(inDeg,0,sizeof inDeg);
            memset(dp,0,sizeof dp);
            for(int i = 1; i <= n ; i++) G[i].clear();
            while(m--)
            {
                int u, v, w;
                cin >> u >> v ;
                
                //if(mp[u][v] == 0)
                G[v].push_back(u);
                
                //G[v].push_back(make_pair((u,w)));
                inDeg[u] ++;
            }
            if(topsort())
            //int maxx = 0;
            for(int i  = 1; i <= ans ; i++)
            printf("%d%c",dp[i]," \n"[i == ans]);
            else 
            puts("-1");
        }
        return 0;
    }
    
    展开全文
  • 原题链接; ...pid=0 这道题看起来啃爹,但是咱们一起来探索一下吧,别看我代码很长,其实不难的。先给你讲个 “鬼” 故事,记得先看完故事再看代码,这样会简单。 这道题其实在讲一个故事,有个人叫XH[i],如果他跟XH...

    原题链接;
    http://codeup.cn/problem.php?cid=100000623&pid=0

    这道题看起来啃爹,但是咱们一起来探索一下吧,别看我代码很长,其实不难的。先给你讲个  “鬼”  故事,记得先看完故事再看代码,这样会简单。
       这道题其实在讲一个故事,有个人叫XH[i],如果他跟XH[j]这个人有关系,
       那肯定是XH[j]被XH[i]打了,这里呢就用A[i][j]表示他们有没有关系,如果A[i][j]=1,就表示他们有关系。另外他们身上都有个标记,表示他被几个人打过,这个标记就是innum,如果XH[i]的innum为0表示这个人他没被人欺负过,他太牛了。另外他们身上还有个标记叫outwith[]表示他们打过谁,打过的人就被标记进他们的outwith[]里面,表示他们的战绩。然后呢,看看谁最牛牛逼,如果他从没被打过,那么他就是最牛逼的,但是你会发现这种人不止一个,怎么办呢,这里就看他们的编号,他们身上还有个标记size表示他们的编号,编号越小,谁就最优先。首先把入度为0(从没被打过)的按编号的最小顺序输出先  入栈 S   ,S是一个栈,但是它也是一个棺材,XH[i]入栈表示他不小心死了,但是 :比如XH[j]被XH[i]打过,现在XH[i]不小心死了,这时XH[j]身上的标记innum要减减,表示打过他的人少一个了。我们说了,这个人不小心死了,但是他会变成鬼,然后去找那些他之前打过的人,而这些人的名字都在他的outwith[]里面记录着.所以他太坏了,死了还想欺负人家。他第一步是出栈,表示他要跳出棺材,仔细想想刚刚编号小的先进棺材的,所以出棺材的时候是编号小的要后出,编号大的要先出。
       他怎么找呢,可能他打过好几个人啊,原来他是按他打人的先后顺序来找,先找到outwith[0],然后再找outwith[1],再找outwith[2],因为outwith[]里面记录着那些人的名字。如果他一找到那个人,那他们就“可能”会决斗,但是要怎么判断他们有没有决斗呢,如果XH[j]被XH[i]打过,但是现在XH[j]因为XH[i]死了,XH[j]它的innum也减1了,也就是打过他的人少一个了,这时如果XH[j]的innum为0了,说明XH[j]很牛逼了,也就是打过他的人都死了,竟然这么牛逼XH[i]就会跟他决斗,由于XH[i]已经是一个鬼魂,他很快就把XH[j]给干掉了。这个时候XH[j]的尸体就会被放入S这个栈里面。
       这说明了什么,如果刚刚XH[j]的innum不为0的话,XH[i]就不会跟他决斗了,因为它觉得XH[j]还不够强大,不配跟他打,然后他就找下一个他打过的人XH[j+1],如果没有了怎么办,也就是XH[i]这个鬼已经找完他之前打过的人了,后面因为他的这种无耻的做法激怒了小编,所以小编让他魂飞魄散了。
       接下来S栈里面,也就是这个棺材里面又跑出一个鬼,他会重复XH[i]这个鬼的操作,最后也被小编给编死了......直到这个棺材里面没有鬼了,故事才结束
    好了接下来看看小编的代码
    #include<iostream>
    using namespace std;
    #include<stack>   //这是栈的头文件,小伙伴如果不想写栈可以用这个东西哦
    #define N 100
    typedef struct node{  //这是一个节点的结构体,节点里面有“入度”,和出边,也就是这个节点能到哪个节点。
        int size;  //这里是标记这是那个节点,是第一个还是第二个
        int innum;  //这是记录这个节点的入度为多少,也就是有多少个点可以到它
        int inwith[N];  //这个不用理
        int outwith[N];  //这里是表示这个点能到哪个点,那么就把那个点加进去
    }node;
    int n;  //这里是有n个点
    int main(){
        cin>>n;
        int A[N][N]={0};  //这是存储输入的那个数组
        node XH[N];     //例如XH[2],表示2这个点
        int i,j,k,t;
        for(i=1;i<=n;i++){
            XH[i].innum=0;  //开始要初始化
            XH[i].size=i-1;  //要让XH[i].innum,XH[i].outwith[j]的值为0,因为结构体是不会帮你默认没赋值的东西为0的
            for(j=0;j<n;j++){
                XH[i].outwith[j]=0;
            }
        }
        for(i=1;i<=n;i++){   //这两个循环是输入来的,同时也稍微做点操作
            k=0,t=0;  //同时也记录了这个点的入度啊,和能到的边啊
            for(j=1;j<=n;j++){
                cin>>A[i][j];  //输入一个数据
                if(A[i][j]){  //如果这个数据不是0,那就说明i是可以到j这个点的
                    XH[j].innum++;  //因为表示i可以到j,那么j这个点的入度是不是要加1呢,是吧,因为有一个点可以到j了嘛
                    XH[i].outwith[t++]=j;//但是i这个点是可以到j的那么就要记录它能到的点,所以把j纳入i里面,其实就是i娶了一个老婆嘛
                }
            }
        }
        stack<node> S;  //这是一个栈的定义,来自于#include<stack> ,例如对于stack<int> S,它是定义一个int型的栈S,那么这里就是定义一个node类型的栈咯
        for(i=1;i<=n;i++){
            if(!XH[i].innum)  //如果这个点的入度为0那么就入栈咯
                S.push(XH[i]);  //这是入栈操作,S是我们刚刚定义的栈,它里面有一个东西叫push(),这个东西是可以压入一个和它相同类型的节点
        }
        int count=0;  //这里是记录有多少个节点 它的度为0
        node temp;  
        int bag[N]={0},gg=0;  //bag[]是存储出栈的节点的,gg只不过是一个普通的变量而已
        while(!S.empty()){  //还记得S吧,我们刚刚定义的,它里面不仅有push()这个东西,还有empty()这个东西,而empty()是判断S栈是否为空
            temp=S.top();  //S栈里面还有个top(),它的作用是获取栈顶元素
            bag[gg++]=temp.size;  //既然栈里面的元素表示度为0的节点,那好了,先获取栈顶元素,把它放进麻袋里,别弄丢了
            S.pop();  //坑爹了,S栈里面还有一个东西叫pop(),表示弹出栈元素,也就是把这个节点删除
            count++;  //这里也记录一下度为0的节点
            for(i=0;temp.outwith[i]!=0;i++){  //记得temp是刚刚那个出栈的元素,它死了,但是你要保留它的灵魂,因为你要找到它认识的人,然后把关系掐断
                XH[ temp.outwith[i] ].innum--;  //首先temp里面是有一个东西叫outwith[]的,我们在开始的结构体已经定义了,它是存储temp这个点能到的点,也就是temp它搞过哪个男的,这些男的也要被记录进outwith[]里面
                if(!XH[ temp.outwith[i] ].innum)  //如果temp搞过的这个男的,如果这个男的的入度也为0,那么就要入栈
                    S.push(XH[ temp.outwith[i] ]);  //把这个被temp搞过的男的,压入栈,因为它的入度为0,也就是它太弱了,它没搞过其他男的
            }
        }
        if(count<n){  //如果度为0的节点不够n个,说明肯定有环啦
        cout<<"ERROR"<<endl;
        }else{
            for(i=0;i<gg;i++){
                if(i!=gg-1)  //这里是确保最后一个数据输出时不含有空格
                cout<<bag[i]<<" ";
                else
                    cout<<bag[i]<<endl;
            }
        }
        return 0;
    }
    
    展开全文
  • 拓扑排序算法例题 1. HDU 3342 ---- 有向图判环 Problem Description ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many ...

    拓扑排序算法例题

    1. HDU 3342 ---- 有向图判环

    Problem Description
    ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many “holy cows” like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost “master”, and Lost will have a nice “prentice”. By and by, there are many pairs of “master and prentice”. But then problem occurs: there are too many masters and too many prentices, how can we know whether it is legal or not?

    We all know a master can have many prentices and a prentice may have a lot of masters too, it’s legal. Nevertheless,some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian’s master and, at the same time, 3xian is HH’s master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not.

    Please note that the “master and prentice” relation is transitive. It means that if A is B’s master ans B is C’s master, then A is C’s master.

    Input
    The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which means x is y’s master and y is x’s prentice. The input is terminated by N = 0.
    TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,…, N-1). We use their numbers instead of their names.

    Output
    For each test case, print in one line the judgement of the messy relationship.
    If it is legal, output “YES”, otherwise “NO”.

    Sample Input

    3 2
    0 1
    1 2
    2 2
    0 1
    1 0
    0 0

    Sample Output

    YES
    NO

    #include <iostream>
    #include <vector>
    #include <queue>
    #include <cstdio>
    #include <string.h>
    using namespace std;
    
    vector<int> stud[102]; //一维数组中的元素是向量,整体则是二维数组 即:stud[0],stud[1],stud[2]...都是向量
    int indegree[102];     //记录各顶点入度
    int n,m;
    queue<int> q;          //记录拓扑排序出来的排列
    
    void Init()
    {   //initialize
    
        int i;
        int x,y;
        memset(indegree,0,sizeof(indegree));
        for(i=0 ; i<102 ; i++)
        {   //记得初始化一维数组(里面储存的是向量)
            //没有初始化就会WA
            stud[i].clear();
        }
        for(i=0 ; i<m ; i++)
        {
            scanf("%d%d",&x,&y);
            stud[x].push_back(y); //在向量stud[x]的末尾添加y
            indegree[y]++;        //y的入度加1
        }
    }
    
    int topo_sort()  //拓扑排序,本次排序的任务是判断最终是否会成环
    {
        for(int i=0 ; i<n ; i++)
            if(indegree[i]==0) q.push(i);
        int cnt=0; //cnt记录取了几次队首元素,用于判断是否有环
        while(!q.empty())
        {
            cnt++;  //非空即取
            int tmp=q.front();
            q.pop();
            for(int i=0 ; i<stud[tmp].size() ; i++)
            {
                int after=stud[tmp][i];  //寻找此点的所有直接后继
                indegree[after]--;       //让它们的入度-1,因为此点已经出队了,指向每个后继结点的线段就少了一条
                if(indegree[after]==0)
                    q.push(after); //如果某个后继结点的入度减到0了,直接入队
            }
        }
        if(cnt<n)
            return -1; //cnt<n,有的结点没有入队,即数据结构中存在环
        else
            return 0;   //正常
    }
    
    int main()
    {
    
        scanf("%d%d",&n,&m);
        while(n!=0)
        {
            Init();
            if(topo_sort()==0)
                printf("YES\n");
            else
                printf("NO\n");
            scanf("%d%d",&n,&m);
        }
        return 0;
    }
    
    

    2. HDU 1285 ---- 确定比赛名次

    Problem Description
    有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。

    Input
    输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示队伍的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。

    Output
    给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。

    其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。

    Sample Input

    4 3
    1 2
    2 3
    4 3

    Sample Output

    1 2 4 3

    #include <iostream>
    #include <vector>
    #include <cstdio>
    #include <queue>
    #include <string.h>
    #include <functional>
    using namespace std;
    int n,m;
    vector<int> team[505];
    int indegree[505];
    //优先队列
    
    
    
    void Init()
    {
        int i;
        for(i=1 ; i<=n ; i++)
            team[i].clear();
        memset(indegree,0,sizeof(indegree));
        int win,lose;
        for(i=1 ; i<=m ; i++)
        {
            scanf("%d%d",&win,&lose);
            team[win].push_back(lose);
            //indegree[win]++;额打错了
            indegree[lose]++;
        }
    }
    
    void topoSort()
    {
        priority_queue<int,vector <int> ,greater <int> >q; //记得加functional头文件
        int i,j;
        //找入度为0的结点,让它们入队
        for(i=1 ; i<=n ; i++)
            if(indegree[i]==0)
                q.push(i);
        //int cnt=0;
        while(!q.empty())
        {
            int tmp=q.top();
            q.pop();
            //cnt++;
            for(j=0 ; j<team[tmp].size() ; j++)
            {   //j必须从0开始,因为访问向量中的元素是要用下标
                int loser=team[tmp][j];
                indegree[loser]--;
                if(indegree[loser]==0)
                    q.push(loser);
            }
            if(!q.empty())
                printf("%d ",tmp);
            else
                printf("%d\n",tmp);
        }
    }
    
    int main()
    {
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            Init();
            topoSort();
        }
        return 0;
    }
    
    

    3.(未完成)POJ 3687 ---- Labeling Balls

    Description

    Windy has N balls of distinct weights from 1 unit to N units. Now he tries to label them with 1 to N in such a way that:

    No two balls share the same label.
    The labeling satisfies several constrains like “The ball labeled with a is lighter than the one labeled with b”.

    Can you help windy to find a solution?

    Input

    The first line of input is the number of test case. The first line of each test case contains two integers, N (1 ≤ N ≤ 200) and M (0 ≤ M ≤ 40,000). The next M line each contain two integers a and b indicating the ball labeled with a must be lighter than the one labeled with b. (1 ≤ a, b ≤ N) There is a blank line before each test case.

    Output

    For each test case output on a single line the balls’ weights from label 1 to label N. If several solutions exist, you should output the one with the smallest weight for label 1, then with the smallest weight for label 2, then with the smallest weight for label 3 and so on… If no solution exists, output -1 instead.

    Sample Input

    5

    4 0

    4 1
    1 1

    4 2
    1 2
    2 1

    4 1
    2 1

    4 1
    3 2

    Sample Output

    1 2 3 4
    -1
    -1
    2 1 3 4
    1 3 2 4

    这题题意一定要看明白,特别绕

    展开全文
  • 数据结构——拓扑排序经典例题

    千次阅读 2019-07-21 11:38:36
    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足...

    定义:
    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

    步骤:

    (1) 选择一个入度为0的顶点并输出;
    (2) 从网中删除此顶点及所有出边。

    如果输出的顶点数小于输入的顶点数,说明这不是一个拓扑序列,该图存在环。

    代码思想:
    用vector存入边的信息,设置一个入度的数组,存入度的数量,

    topsort函数:
    用队列存拓扑序列,先把入度为0的顶点全部入队,取出队列第一个点,输出顶点并把这个顶点的所有出边的入度-1,并判断是不是有新的入度为0的顶点,如果有则入队。直至队列中的所有顶点输出。

    例题1:
    确定比赛名次
    输出一个拓扑序列,并且字典序小的先输出。(此题保证不存在环)

    思路:把模板的队列改成优先队列(有小到大)。

    #include<iostream>
    #include<cstring>
    #include<queue>
    #include<functional>
    #include<vector>
    using namespace std;
    typedef long long ll;
    const int maxn=510;
    vector<int>vec[maxn];
    int du[maxn];
    int n,m;
    
    void topsort()
    {
    	priority_queue<int,vector<int>,greater<int> > s;
    	int flag=0;
    	while(!s.empty())
    		s.pop();
    	for(int i=1;i<=n;i++)
    	{
    		if(!du[i])
    			s.push(i);
    	}
    	while(!s.empty())
    	{
    		int now=s.top();
    		if(flag==0)
    		{
    			cout<<now;
    			flag=1;
    		}
    		else
    			cout<<" "<<now;
    		s.pop();
    		for(int i=0;i<vec[now].size();i++)
    		{
    			if(--du[vec[now][i]]==0)	
    				s.push(vec[now][i]);
    		}
    	}
    }
    int main()
    {
    	while(cin>>n>>m)
    	{
    		memset(du,0,sizeof(du));
    		for(int i=1;i<=n;i++)
    			vec[i].clear();
    		for(int i=1;i<=m;i++)
    		{
    			int a,b;
    			cin>>a>>b;
    			vec[a].push_back(b);
    			du[b]++;
    		}
    		topsort();
    		cout<<endl;
    	}
    	return 0;	
    } 
    

    例题2:只是判断是否存在环

    Legal or Not

    思路:用拓扑排序就可以判断是否为环。

    #include<iostream>
    #include<vector>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int maxn=110;
    int n,m;
    vector<int>vec[maxn];
    queue<int>s;
    int du[maxn];
    bool topsort()
    {
    
    	int num=0;
    	while(!s.empty())	
    		s.pop();
    	for(int i=0;i<n;i++)
    	{
    		if(!du[i])
    			s.push(i);
    	}
    	while(!s.empty())
    	{
    		int ans=s.front();
    		s.pop();
    		num++;
    		for(int i=0;i<vec[ans].size();i++)
    		{
    			if(--du[vec[ans][i]]==0)
    				s.push(vec[ans][i]);
    		}
    	}
    	//cout<<num<<endl;
    	if(num==n)	return true;
    	return false;
    }
    int main()
    {
    	while(cin>>n>>m,n,m)
    	{
    		memset(du,0,sizeof(du));
    		for(int i=0;i<n;i++)
    			vec[i].clear();
    		for(int i=1;i<=m;i++)
    		{
    			int a,b;
    			cin>>a>>b;
    			vec[a].push_back(b);
    			du[b]++;
    		}
    		if(topsort()) cout<<"YES"<<endl;
    		else cout<<"NO"<<endl;
    	}
    	return 0;
     } 
    

    例题3:
    Almost Acyclic Graph

    给你m条边,不确定有没有环,删除一条边,看是否可以构成有向无环图。

    还是判环,我们如果删除每一条边,再进行拓扑排序,时间到了1e7级别,估计会超时。

    正解:O(n*m)得到做法,topsort函数不变,记录每一个顶点入度的次数,我们只需要每一次尝试入度大于等于1的顶点-1,尝试一下拓扑排序,因为入度-1,说明其中的某一条边给删掉了,尝试每一个入度>=1的点就可以得到答案。为啥不尝试入度为0的点,因为入度为0的点这条边构不成环,自己可以想想。

    #include<iostream>
    #include<cstring>
    #include<queue>
    #include<vector>
    using namespace std;
    const int maxn=1000;
    typedef long long ll;
    ll rudeg[maxn],indeg[maxn];//ru为标准 in为操作 
    vector<ll> vec[maxn];
    ll n,m;
    int  topsort()
    {
    	queue<ll> q;
    	while(!q.empty()) q.pop();
    	for(int i=1;i<=n;i++)
    	{	
    		if(!indeg[i]) 
    			q.push(i);
    	}
    	ll num=0;
    	while(!q.empty())
    	{
    		ll t=q.front();
    		q.pop();
    		num++;
    		for(int i=0;i<vec[t].size();i++)
    		{
    			if(--indeg[vec[t][i]]==0)
    			{
    				q.push(vec[t][i]);
    			}
    		}
    	}
    	if(num==n)	return 1;
    	return 0;
    }
    int main()
    {
    	while(cin>>n>>m)
    	{
    		for(int i=0;i<=n;i++)
    			vec[i].clear();
    		ll flag=0; 
    		memset(rudeg,0,sizeof(rudeg));
    		memset(indeg,0,sizeof(indeg));
    		for(int i=1;i<=m;i++)
    		{
    			ll a,b;
    			cin>>a>>b;
    			vec[a].push_back(b);
    			indeg[b]++;
    			rudeg[b]++; 
    		}
    		if(topsort())
    		{
    			flag=1;
    		}
    		else
    		{
    			for(int i=1;i<=n;i++)
    			{
    				for(int i=1;i<=n;i++)
    					indeg[i]=rudeg[i];
    				if(indeg[i]>=1)
    				{
    					indeg[i]--;
    					if(topsort())
    					{
    						flag=1;
    						break;
    					}
    				}
    			}
    		}
    		if(flag)
    			cout<<"YES"<<endl;
    		else
    			cout<<"NO"<<endl;
    	}
    	return 0;
     } 
    

    例题4:
    reward

    也是一个拓扑序列,每个人基础888元,a->b 说明a要比b大1(贪心的思想)。
    也就是b->a a的层数比b大1层 总金额=前一个金额+1;

    #include<iostream>
    #include<queue>
    #include<vector>
    #include<cstring>
    using namespace std;
    const int maxn=2e4+10;
    vector<int>vec[maxn];
    queue<int> q;
    int n,m;
    int du[maxn],money[maxn],num,sum;
    
    void topsort()
    {
    	while(!q.empty()) q.pop();
    	
    	for(int i=1;i<=n;i++)
    	{
    		if(!du[i])	
    		{
    			q.push(i);
    			money[i]=888;
    		}
    	}
    	
    	num=0;
    	sum=0;
    	while(!q.empty())
    	{
    		int now=q.front();
    		sum+=money[now];
    		q.pop();
    		num++;
    		for(int i=0;i<vec[now].size();i++)
    		{
    			if(--du[vec[now][i]]==0)	
    			{
    				q.push(vec[now][i]);
    				money[vec[now][i]]=money[now]+1;
    			}
    		 } 
    	}
    	if(num==n)
    		cout<<sum<<endl;
    	else
    		cout<<"-1"<<endl;
    }
    int main()
    {
    	while(cin>>n>>m)
    	{
    		memset(du,0,sizeof(du));
    		memset(money,0,sizeof(money));
    		for(int i=0;i<n;i++)
    		{
    			vec[i].clear();
    		}
    		
    		for(int i=1;i<=m;i++)
    		{
    			int a,b;
    			cin>>a>>b;
    			vec[b].push_back(a);
    			du[a]++;
    		}
    		
    		topsort();
    	}
    	return 0;
    }
    
    展开全文
  • 拓扑排序(附例题

    2021-11-23 15:19:06
    ACWING848 拓扑排序 给定一个 n nn 个点 m mm 条边的有向图,点的编号是 1 11 到 n nn,图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 − 1 -1−1。 若一个由图中所有点...
  • 拓扑排序讲解+例题

    2021-03-04 19:27:24
    对一个==有向无环图(Directed Acyclic Graph简称DAG)==G进行拓扑排序,是将G中所有顶点排成一个线性序列, 使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。 通常,这样的线性序列...
  • 拓扑排序应用:拓扑排序是应用在有向图中,对所有的节点进行排序。 思路: 1.首先统计所有节点的入度,把其加入一个入度表中; 2.维护一个队列,讲入度为0的节点入队;并且维护一个邻接表用于存储每个节点相关联...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,719
精华内容 687
关键字:

拓扑排序例题