精华内容
下载资源
问答
  • 拓扑排序判环

    2019-05-15 22:03:14
    拓扑排序过程   在一个有向图中选择一个入度为零的点并且输出,从图(vector建图)中删除这个点和所有以它为尾的边,一直重复上述过程直到不存在没有前驱的顶点。如果此时输出的顶点数小于有向图中的顶点数,说明图中...
    • 拓扑排序过程
        在一个有向图中选择一个入度为零的点并且输出,从图(vector建图)中删除这个点和所有以它为尾的边,一直重复上述过程直到不存在没有前驱的顶点。如果此时输出的顶点数小于有向图中的顶点数,说明图中存在环,否则输出的顶点序列是拓扑序列。
    //二分+拓扑排序(离线计算)
    #include<cstdio>
    #include<cstdlib>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<queue>
    #include<vector>
    #define pi 3.1415926
    #define mod 1000000007
    using namespace std;
    
    //typedef pair<int,int> Node;
    typedef long long LL;
    const int Max_n=100005;
    int n,m;
    int in[Max_n];//每个点的入度
     
    struct Edge{
    	int s,e;
    }edge[Max_n<<1];//m<2*10^5 
    
    int check(int mid){//拓扑排序判环
    	memset(in,0,sizeof(in));
    	vector<int>v[Max_n];
    	for(int i=1;i<=mid;i++){//mid及mid之前的数据是否存在环 
    		v[edge[i].s].push_back(edge[i].e);//建图(类似与邻接表)
    		in[edge[i].e]++; 
    	} 
    	int sum=0;//拓扑排序所有能够出来的点的总数 
    	queue<int>q;
    	for(int i=1;i<=n;i++)//如果有入度为0的点,则加入到队列中 
    		if(!in[i]) q.push(i);	 
    	while(q.size()){
    		int x=q.front();q.pop();//入度为0的点出队
    		sum++;//总数+1
    		for(unsigned int i=0;i<v[x].size();i++){//注意这里从0开始 
    			//所有与x相连接的点入度-1
    			in[v[x][i]]--;
    			if(in[v[x][i]]==0) q.push(v[x][i]); 
    		}
    	} 
    	return sum==n;//出来的所有点的总数为n说明不存在环,否则存在环 
    } 
    
    int main(){
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=m;i++)
    		scanf("%d%d",&edge[i].s,&edge[i].e);
    	int l=1,r=m,ans;
    	while(l<=r){
    		int mid=l+(r-l)/2;
    		if(check(mid)){//此时中点前面不存在环,存在环的点在右边 
    			l=mid+1;
    			ans=mid;//记录不存在环的最后一个点 
    		}else{//中点之前存在环 
    			r=mid-1;
    		} 
    	}
    	for(int i=1;i<=ans;i++) printf("Yes\n"); 
    	for(int i=ans+1;i<=m;i++) printf("No\n");
    	return 0;
    } 
    

    hdu1285:确定比赛名次

    theme:n只队伍比赛,给定m次比赛的结果:p1 p2表示队伍p1赢了p2,请将n只队伍按排名先后输出,如果有多种答案,则先输出编号最小的。

    solution:赢了的队伍肯定先输出,所以按p1->p2建图,由于最后输出时位于同一级时先输出编号小的,所以用优先队列模拟最小堆,将度为0的编号按从小到大输出即可。

    #include<bits/stdc++.h>
    using namespace std;
    #define pb(x) push_back(x)
    #define far(i,t,n) for(int i=t;i<n;++i)
    typedef long long ll;
    typedef unsigned long long ull;
    using namespace std;
    
    struct _a
    {
        int p1,p2;
    }a[550];
    
    int in[550];
    int n,m;
    
    void check()
    {
        memset(in,0,sizeof(in));
        vector<int>v[550];
        far(i,0,m)//p2<p1
            v[a[i].p1].push_back(a[i].p2),in[a[i].p2]++;
        priority_queue<int,vector<int>,greater<int>>q;
        far(i,1,n+1)
            if(in[i]==0)
                q.push(i);
        int flag=0;
        while(!q.empty())
        {
            int u=q.top();
            q.pop();
            if(flag==0)
                printf("%d",u),flag=1;
            else
                printf(" %d",u);
            int s=v[u].size();
            far(i,0,s)
            {
                int t=v[u][i];
                in[t]--;
                if(in[t]==0)
                    q.push(t);
            }
        }
        puts("");
    }
    
    int main()
    {
        while(~scanf("%d%d",&n,&m))
        {
            far(i,0,m)
                scanf("%d%d",&a[i].p1,&a[i].p2);
            check();
        }
    }

    D. Gourmet choice

    theme:给定两堆物品,第一堆有n个,第二堆有m个,现给定n*m的矩阵,矩阵仅由>、<、=组成,表示第一堆的第i个物品的价值>/</=第二堆的第j个物品。现让你用最少的数字给这n+m个物品编号,使得序号满足矩阵中的大小关系。

    solution:如果没有=的话,那就是裸的拓扑排序,有=的话,我们可以先用并查集将价值相等的物品归为一个节点,再使用拓扑排序按度为0的顺序编号。

    #include<bits/stdc++.h>
    using namespace std;
    #define pb(x) push_back(x)
    #define far(i,t,n) for(int i=t;i<n;++i)
    typedef long long ll;
    typedef unsigned long long ull;
    using namespace std;
    
    int fa[3000];
    
    int Find(int x)
    {
        return fa[x]==x?x:fa[x]=Find(fa[x]);
    }
    
    void unit(int x,int y)
    {
        x=Find(x);
        y=Find(y);
        fa[y]=x;
    }
    
    char a[1010][1010];
    int ans[3010];
    int vis[3030];
    int in[3000];
    int n,m;
    
    void check(){//拓扑排序
    	memset(in,0,sizeof(in));
    	memset(ans,0,sizeof(ans));
    	memset(vis,0,sizeof(vis));
    	vector<int>v[3000];
    	far(i,1,n+1)//建图
            far(j,1,m+1)
            {
                if(a[i][j]=='>')
                    v[Find(j+n)].push_back(Find(i)),in[Find(i)]++;
                else if(a[i][j]=='<')
                    v[Find(i)].push_back(Find(j+n)),in[Find(j+n)]++;
            }
    	queue<int>q;
    	for(int i=1;i<=n+m;i++)//如果有入度为0的点,则加入到队列中
    		if(!in[Find(i)])
            {
                int y=Find(i);
                if(!vis[y])//注意这里的判断,否则会重复加入
                {
                    q.push(y);
                    ans[y]=1;
                    vis[y]=1;
                }
            }
    	while(q.size()){
    		int x=q.front();q.pop();//入度为0的点出队
    		x=Find(x);
    		for(unsigned int i=0;i<v[x].size();i++){//注意这里从0开始
    			//所有与x相连接的点入度-1
    			int y=Find(v[x][i]);
    			in[y]--;
    			if(in[y]==0)
                {
                    q.push(y);
                    ans[y]=ans[x]+1;
                    vis[y]=1;
                }
    		}
    	}
    	far(i,1,n+m+1)//说明存在环,该节点不可能度为0
            if(!vis[Find(i)])
            {
                puts("No");
                return;
            }
        puts("Yes");
        far(i,1,n+1)
            printf("%d ",ans[Find(i)]);
        puts("");
        far(i,1,m+1)
            printf("%d ",ans[Find(n+i)]);
        puts("");
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        far(i,1,n+1)
            scanf("%s",a[i]+1);
        far(i,1,n+m+1)
            fa[i]=i;
        far(i,1,n+1)
            far(j,1,m+1)
                if(a[i][j]=='=')
                    unit(i,j+n);
        check();
    }

     

    展开全文
  • 简单拓扑排序判环 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,...

    Legal or Not

    简单拓扑排序判环
    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<stdio.h>
    #include<algorithm>
    #include<cstring>
    #include<queue>
    using namespace std;
    int main()
    {
    	int n,m,a[101][101],du[101],i,x,y;
    	while(scanf("%d%d",&n,&m),m!=0||n!=0)
    	{
    		memset(a,0,sizeof(a));
    		memset(du,0,sizeof(du));
    		for(i=0;i<m;i++)
    		{
    			scanf("%d%d",&x,&y);
    			if(a[x][y]==0){//注意只有当两点没有关系时,入度++ 
    				a[x][y]=1;
    			du[y]++;
    			}
    			
    		}
    		queue<int>q;
    		for(i=0;i<n;i++)
    		{
    			if(du[i]==0)q.push(i);
    		}
    		int cout=0;
    		while(!q.empty())
    		{
    			int tem=q.front();
    			q.pop();
    			for(i=0;i<n;i++)//如果有与队列中的点有连线的点,取消连线,入度-- 
    			{
    				if(a[tem][i]!=0){
    					a[tem][i]=0;
    				du[i]--;
    				if(du[i]==0)q.push(i);
    				}
    				
    			}	
    				cout++;
    		}
    		if(cout==n)printf("YES\n");//计数当从队列中输出了n个数,合法 
    		else printf("NO\n");	
    	}
    	return 0;
     } 
    
    展开全文
  • 拓扑排序判环 题目大意: 两个题一样 有向图判断是否有环







    3342: http://acm.split.hdu.edu.cn/showproblem.php?pid=3342

    5154:http://acm.split.hdu.edu.cn/showproblem.php?pid=5154










    题目大意:

    两个题一样    有向图判断是否有环









    分析:

    拓扑排序











    AC代码:

    #include <iostream>
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <vector>
    #include <stack>
    #include <queue>
    #include <map>
    #include <set>
    #include<list>
    #include <bitset>
    #include <climits>
    #include <algorithm>
    #define gcd(a,b) __gcd(a,b)
    #define FIN		freopen("input.txt","r",stdin)
    #define FOUT 	freopen("output.txt","w",stdout)
    typedef long long LL;
    const LL mod=1e9+7;
    const int INF=0x3f3f3f3f;
    const double PI=acos(-1.0);
    using namespace std;
    int head[105],indeg[105];
    int cnt;
    int n,m;
    struct node{
    	int next;
    	int to;
    }edge[105];
    void add(int u,int v){
    	edge[cnt].to=v;
    	edge[cnt].next=head[u];
    	head[u]=cnt++;
    }
    int topo(){
    	queue<int> Q;
    	for (int i=0;i<n;i++) if (indeg[i]==0) Q.push(i);
    	int k=0;
    	while (!Q.empty()){
    		int u=Q.front();
    		Q.pop();k++;
    		for (int i=head[u];i!=-1;i=edge[i].next){
    			int v=edge[i].to;
    			indeg[v]--;
    			if (indeg[v]==0) Q.push(v);
    		}
    	}
    	if (k<n) return 0;
    	return 1;
    }
    int main (){
    	while (scanf ("%d%d",&n,&m)&&n){
    		int x,y;
    		memset(indeg,0,sizeof(indeg));
    		memset(head,-1,sizeof(head));
    		cnt=0;
    		for (int i=0;i<m;i++){
    			scanf ("%d%d",&x,&y);
    			add(x,y);
    			indeg[y]++;
    		}
    		if (topo()) printf ("YES\n");
    		else printf ("NO\n");
    	}
    	return 0;
    } 








    AC代码:

    #include <iostream>
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <vector>
    #include <stack>
    #include <queue>
    #include <map>
    #include <set>
    #include<list>
    #include <bitset>
    #include <climits>
    #include <algorithm>
    #define gcd(a,b) __gcd(a,b)
    #define FIN		freopen("input.txt","r",stdin)
    #define FOUT 	freopen("output.txt","w",stdout)
    typedef long long LL;
    const LL mod=1e9+7;
    const int INF=0x3f3f3f3f;
    const double PI=acos(-1.0);
    using namespace std;
    int head[105],indeg[105];
    int cnt;
    int n,m;
    struct node{
    	int next;
    	int to;
    }edge[10005];
    void add(int u,int v){
    	edge[cnt].to=v;
    	edge[cnt].next=head[u];
    	head[u]=cnt++;
    }
    int topo(){
    	queue<int> Q;
    	for (int i=1;i<=n;i++) if (indeg[i]==0) Q.push(i);
    	int k=0;
    	while (!Q.empty()){
    		int u=Q.front();
    		Q.pop();k++;
    		for (int i=head[u];i!=-1;i=edge[i].next){
    			int v=edge[i].to;
    			indeg[v]--;
    			if (indeg[v]==0) Q.push(v);
    		}
    	}
    	if (k<n) return 0;
    	return 1;
    }
    int main (){
    	while (scanf ("%d%d",&n,&m)!=EOF){
    		int x,y;
    		memset(indeg,0,sizeof(indeg));
    		memset(head,-1,sizeof(head));
    		cnt=0;
    		for (int i=0;i<m;i++){
    			scanf ("%d%d",&x,&y);
    			add(x,y);
    			indeg[y]++;
    		}
    		if (topo()) printf ("YES\n");
    		else printf ("NO\n");
    	}
    	return 0;
    } 

    展开全文
  • ... 就是拓扑排序判断是否有环,有环就输出NO,没有就输出YES。...拓扑排序判环,用队列实现的话就是看出现在队列中的元素是否跟顶点数相同,如果不同的话肯定是存在环的,因为如果最后只剩下环,那么并不存在一个入度

    http://acm.hdu.edu.cn/showproblem.php?pid=3342

    http://acm.hdu.edu.cn/showproblem.php?pid=5154

    就是拓扑排序判断是否有环,有环就输出NO,没有就输出YES。

    拓扑排序判环,用队列实现的话就是看出现在队列中的元素是否跟顶点数相同,如果不同的话肯定是存在环的,因为如果最后只剩下环,那么并不存在一个入度为0的点。

    还有一点特别重要的就是一定要初始化!!!!!!!!对入度数组,以及vector进行初始化!!!!!!又白白贡献一次WA

    hdu 5514 :

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    using namespace std;
    #define M 10009
    int in[M];
    vector<int> G[M];
    int n,m;
    bool toposort()
    {
        queue<int> q;
        int j = n;
        for(int i = 1;i <= n;i++)
        {
            if(!in[i])
                q.push(i);
        }
        while(!q.empty())
        {
            int cur = q.front();
            q.pop();
            j--;
            for(int i = 0;i < G[cur].size();i++)
            {
                in[G[cur][i]]--;
                if(in[G[cur][i]]==0)
                q.push(G[cur][i]);
            }
        }
        if(j>0) return false;
        return true;
    }
    int main()
    {
        while(scanf("%d %d",&n,&m)==2)
        {
            memset(in,0,sizeof(in));
            for(int i = 1;i <= n;i++)
                G[i].clear();
            for(int i = 0;i < m;i++)
            {
                int a,b;
                scanf("%d %d",&a,&b);  //b before a
                in[a]++;
                G[b].push_back(a);
            }
            bool ok = toposort();
            if(ok) printf("YES\n");
            else printf("NO\n");
        }
        return 0;
    }
    


    hdu 3342:

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <queue>
    #include <vector>
    using namespace std;
    #define M 1000
    int in[M];
    vector<int> G[M];
    int n,m;
    bool toposort()
    {
        queue<int> q;
        int j = n;
        for(int i = 0;i < n;i++)
        {
            if(!in[i]) q.push(i);
        }
        while(!q.empty())
        {
            int t = q.front();
            q.pop();
            j--;
            for(int i = 0;i < G[t].size();i++)
            {
                in[G[t][i]]--;
                if(in[G[t][i]]==0)
                    q.push(G[t][i]);
            }
        }
        if(j > 0) return false;
        return true;
    }
    int main()
    {
        while(cin >> n >> m && n)
        {
            memset(in,0,sizeof(in));
            for(int i = 0;i < n;i++)
                G[i].clear();
            for(int i = 0;i < m;i++)
            {
                int a,b;
                cin >> a >> b;
                in[b]++;
                G[a].push_back(b);
            }
            bool ok = toposort();
            if(ok) cout << "YES\n";
            else cout << "NO\n";
        }
        return 0;
    }
    



    展开全文
  • 题意:老板给n个人发工资,...分析:知道了最少888元,最多的不知道,构造反向图即可,用拓扑排序判环 代码: #include #include #include #include #include #include #include #include #include #include
  • 题目链接http://acm.hdu.edu.cn/showproblem.php?pid=3342题意在某个大牛qq群中,一些大牛喜欢自称某某某是他的师傅,某某某是他...思路拓扑排序判环:当拿出来的点不足n个,说明有环。#include #include #include #in
  • 分析: 拓扑排序判环 + 判唯一性 本题特别的地方在 第几组能够确定唯一的拓扑序列,所以每输入一组关系,需调用拓扑排序一次,若确定了存在唯一序列或者存在环,即可不再调用。 若直到输入完毕也不能确定,输出...
  • 解题思路:拓扑排序判环模板题 AC代码: #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;cstdlib&gt; #include &lt;cmath&gt; #include &lt;iostream&gt...
  • 题目大意:问所给的边中,有没有出现环解题思路:拓扑排序判环了#include #include #include #include #include #include #include using namespace std; const int N = 10010;st
  • /*题意:给你一个有向图, 一共有n个节点 , m条边, 一条路上的价值为这个路上出现过的某个字符最多出现次数, 现求这个最大价值, 如果价值可以无限大就输出-1。...拓扑排序判环+DAG上dp+记忆化搜索 状态:dp[i]
  • 说白了就是拓扑排序判环问题,对于给出的n个人作为图G的n个顶点,他们之间的关系看做是有向边,对于有向图G来说,如果拓扑序列存在,那么就说明这n个人之间的师徒关系合法,否则不合法。 代码如下:用了vector和...
  • 题意:n个人,m个师徒关系,判断这m种师徒关系是否合法(如a既是b...思路:拓扑排序判环 AC代码: #include #include #include #include #include #include #include #include #include #include using nam
  • 但是枚举边O(m),拓扑排序O(n+m),总复杂度O(m*(n+m)),没办法过. 删除一条边,在拓扑排序中的影响其实只是这条边出点的度数在跑之前减少了1, 那么其实我们枚举度数减少的点就行了. 枚举点的复杂度只有O(n),那么总...
  • 题意:给你一个n个点m条边的有向图,每一个顶点都对应一个字母,定义一条路径的价值为:从一个顶点开始这...分析: 拓扑排序判环 + dp 拓扑排序 :  由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到
  • //实现拓扑排序的 关键点 } } if (sum == n) return 1 ; else return 0 ; } int main() { t = read(); for ( int i = 1 ; i ; i++ ){ cin >> n >> m; memset(ind, 0 , sizeof (ind)...
  • 小明的实验室有N台电脑,编号1~N。原本这N台电脑之间有N-1条数据链接相连,恰好构成一个树形网络。在树形网络上,任意两台电脑之间有唯一的路径相连。 不过在最近一次维护网络时,管理员误操作使得某两台电脑之间...
  • 右)判断有无的出现方法:直接拓扑排序,如果能正常排序完,这个就是无的有向图DAG,如果不能,在拓扑排序的过程中有些点的入度经过去边操作之后一直不为零,就是有的存在。csdn的输入体验太糟糕了code将就着看...
  • 这道题其实就是一个拓扑排序判圈,我的博客里面其他几篇拓扑排序判圈的套路一样。但是这道题与他们不同的的是在大小关系里面存在一种 “=”的关系,这就意味的那些序号不同的点,实际上是一个点。共享入度和出度。...
  • 第三题判断的存在有一万种方式,拓扑排序,甚至撸上去一个tarjan都行,非自己图快意淫出一个不存在的递归算法然后把心态调崩了。。导致只拿了五十分。 100分: #include <bits/stdc++.h> using namespace...
  • 题解 ... 思路 : 很明显强调顶点之间的依赖关系 , 是一个典型的拓扑排序 , 跑一边拓扑 , 统计一下删除的顶 点个数是否是总数 , 也就是说有没有把所有顶点全删除 , 如果没有那就存在 . 代码 这...
  • 使用拓扑排序判环即可 代码 # include using namespace std ; # define mem(a, b) memset(a, b, sizeof(a)) const int N = 2020 ; vector < int > e1 [ N ] ; vector < int > e2 [ N ] ;...
  • Legal or Not 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 ....
  • 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-l...

空空如也

空空如也

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

拓扑排序判环