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

    2018-06-14 23:35:23
    给你一个N点和M条有向边的图,问你该图是否可拓扑排序.#include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; ...
    
    

    给你一个N点和M条有向边的图,问你该图是否可拓扑排序.

    #include<cstdio>  
    #include<cstring>  
    #include<vector>  
    #include<queue>  
    using namespace std;  
    const int maxn=100+10;  
    int n,m;  
    vector<int> G[maxn];//G[i]表示i节点所指向的所有其他点  
    int in[maxn];//节点入度  
    bool topo()//判断该图是否可拓扑排序  
    {  
        queue<int> Q;  
        int sum=0;//记录可拆解的点数目  
        for(int i=0;i<n;i++)if(in[i]==0)  
            Q.push(i);  
        while(!Q.empty())  
        {  
            int u=Q.front(); Q.pop();  
            sum++;  
            for(int i=0;i<G[u].size();i++)  
            {  
                int v=G[u][i];  
                if(--in[v]==0) Q.push(v);  
            }  
        }  
        return sum==n;//可完全拓扑  
    }  
    int main()  
    {  
        while(scanf("%d%d",&n,&m)==2&&n)  
        {  
            memset(in,0,sizeof(in));  
            for(int i=0;i<n;i++) G[i].clear();  
            for(int i=0;i<m;i++)  
            {  
                int u,v;  
                scanf("%d%d",&u,&v);  
                G[u].push_back(v);  
                in[v]++;  
            }  
            printf("%s\n",topo()?"YES":"NO");  
        }  
        return 0;  
    }  

    展开全文
  • 我们直接先把所有的有向边建图,然后拓扑排序判断环,如果此时有环那么直接输出no 为了将无向边变成有向边之后依旧无环,那么我们只需要遵循拓扑排序的规则,给无向图指定方向的时候对于每条边,从拓扑序小的点指向...

    整理的算法模板合集: ACM模板


    luogu链接
    在这里插入图片描述

    我们直接先把所有的有向边建图,然后拓扑排序判断环,如果此时有环那么直接输出no
    为了将无向边变成有向边之后依旧无环,那么我们只需要遵循拓扑排序的规则,给无向图指定方向的时候对于每条边,从拓扑序小的点指向拓扑序大的点,就一定保证无环。

    要注意的是本题的数据范围比较大,如果用memset把topo数组初始化的话就会TLE,但是我们实际上是不用考虑topo数组的初始化的,因为我们一直是往上覆盖的。

    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<iostream>
    #include<queue>
    using namespace std;
    typedef long long ll;
    typedef pair<int, int> PII ;
    const int N = 500007, M = 5000007, INF = 0x3f3f3f3f;
    
    int n, m;
    int head[N], ver[M], nex[M], edge[M], tot;
    int topo[N], din[N];
    int cnt;
    
    void add(int x, int y){
        ver[tot] = y;
        nex[tot] = head[x];
        head[x] = tot ++ ;
        din[y] ++ ;
    }
    
    bool toposort(int x)
    {
        queue<int>q;
        for(int i = 1; i <= n; ++ i)
            if(din[i] == 0)q.push(i);//入度为0的先入队
        while(q.size())
        {
            int x = q.front();
            q.pop();
            topo[x] = ++ cnt;//拓扑序
            for(int i = head[x]; ~i; i = nex[i]){
                int y = ver[i];
                if( -- din[y] == 0){
                    q.push(y);
                }
            }
        }
        if(cnt < n)return false;
        return true;
    }
    
    int main()
    {
        int t ;
        scanf("%d", &t);
        while(t -- ){
            scanf("%d%d", &n, &m);
            memset(head, -1, sizeof head);
            memset(din, 0, sizeof din);
            tot = cnt = 0;
            vector<PII> v;
            for(int i = 1; i <= m; ++ i){
                int x, y, op;
                scanf("%d%d%d", &op, &x, &y);
                if(op == 1)add(x, y);
                else v.push_back({x, y});
            }
            if(!toposort(n)){
                puts("NO");
                continue;
            }
            puts("YES");
            for(int x = 1; x <= n; ++ x)
            for(int i = head[x]; ~i; i = nex[i]){
                int y = ver[i];
                printf("%d %d\n", x, y);
            }
            for(int i = 0; i < (int)v.size(); ++ i){
                int x = v[i].first, y = v[i].second;
                if(topo[x] < topo[y])
                    printf("%d %d\n", x, y);
    //只要满足拓扑序,从拓扑序小的指向拓扑序大的就一定没有环
                else printf("%d %d\n", y, x);
            }
        }
        return 0;
    }
    
    
    展开全文
  • 拓扑排序判断有向的题目,对于判的题,判无向一般用并查集,判有向一般用拓扑排序 #include <bits/stdc++.h> using namespace std; int main(){ int v,e,in[105],x,y; vector<int> adjl...

    题目

     

    拓扑排序判断有向环的题目,对于判环的题,判无向环一般用并查集,判有向环一般用拓扑排序

     

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        int v,e,in[105],x,y;
        vector<int> adjl[105];
        bool vis[105];
        while(cin>>v>>e,v!=0){
            memset(adjl,0,sizeof(adjl));
            memset(vis,0,sizeof(vis));
            memset(in,0,sizeof(in));
            for(int i=0;i<e;i++){
                cin >> x >>y;
                in[y]++;
                adjl[x].push_back(y);
            }
            int cnt = v;
            
            queue<int> q;
            for(int i=0;i<v;i++){
                if(in[i] ==0){
                    q.push(i);
                    vis[i] = true;
                }
            }
            while(!q.empty()){
                int tmp = q.front();
                q.pop();
                cnt--;
                for(int i=0;i<adjl[tmp].size();i++){
                    int kk =adjl[tmp][i];
                    in[kk]--;
                    if(in[kk]==0&&!vis[kk]){
                        q.push(kk);
                        vis[kk] = true;
                    } 
                }
            }
    //        while(!q.empty()){
    //            int vt=q.front();
    //           // cout<<vt<<endl;
    //            q.pop();cnt--;
    //            for(int i=0;i<adjl[vt].size();i++)
    //            {
    //                int vv=adjl[vt][i];
    //                in[vv]--;
    //                if(!vis[vv]&&in[vv]==0)
    //                {
    //                    q.push(vv);
    //                    vis[vv]=true;
    //                }
    //            }
    //        }
    
            if(cnt == 0)
                cout << "YES" << endl;
            else 
                cout << "NO" << endl;
            
        }
        return 0;
    } 

     

    展开全文
  • 题意不多说,判断环,无向图用并查集,有向图用拓扑; 有向图判断有没有环,利用节点数和边数的关系,一步步去除如度为0的节点,可以完全去除说明没有环。反之亦然。 #include using namespace std; int n,m,a,b; ...

    Legal or Not

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 10447    Accepted Submission(s): 4904


    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

    题意不多说,判断环,无向图用并查集,有向图用拓扑;

    有向图判断有没有环,利用节点数和边数的关系,一步步去除如度为0的节点,可以完全去除说明没有环。反之亦然。

    #include<bits/stdc++.h>
    using namespace std;
    
    int n,m,a,b;
    vector<int> v[105];
    int in[105],vis[105];
    int main()
    {
    	while(~scanf("%d%d",&n,&m),n)
    	{
    		for(int i=0; i<103; i++)v[i].clear();
    		memset(in,0,sizeof(in));
    		memset(vis,0,sizeof(vis));
    		for(int i=0; i<m; i++)
    		{
    			scanf("%d%d",&a,&b);
    			v[a].push_back(b);
    			in[b]++;
    		}
    		int count=n;
    		queue<int> q;
    		for(int i=0; i<n; i++)
    		{
    			if(in[i]==0)
    			{
    				q.push(i);
    				vis[i]=1;
    			}
    		}
    		while(!q.empty())
    		{
    			int k=q.front();
    			count--;
    			q.pop();
    			for(int i=0; i<v[k].size(); i++)
    			{
    				int x=v[k][i];
    				in[x]--;
    				if(in[x]==0&&!vis[x])
    				{
    					q.push(x);
    					vis[x]=1;
    				}
    			}
    		}
    		if(count==0)printf("YES\n");
    		else printf("NO\n");
    	}
    	return 0;
    }

    展开全文
  • 图结构练习——判断给定图是否存在合法拓扑序列 Time Limit: 1000MS Memory limit: 65536K 题目描述  给定一个有向图,判断该有向图是否存在一个合法的拓扑序列。 输入  输入包含多组...
  • 就会拓扑模板题 直接代码: #include #include #define MAX 110 int graph[MAX][MAX] , in[MAX]; bool visited[MAX] ; int main() { int m,n; while(~scanf("%d%d",&n,&m) && n) { memset(graph,0,...
  • 拓扑排序

    2019-05-15 22:03:14
    拓扑排序过程   在一个有向图中选择一个入度为零的点并且输出,从图(vector建图)中删除这个点和所有以它为尾的边,一直重复上述过程直到不存在没有前驱的顶点。如果此时输出的顶点数小于有向图中的顶点数,说明图中...
  • AOV网,判断网中是否存在 否则打印出拓扑序列
  • dfs解拓扑排序在无情况下很方便,反向存边然后dfs即可。但要判断有没有时,需要用回溯的思路:对每个点dfs,若无,回溯时将这个点视为安全。具体操作时,存一个flag,dfs进入时让它为1,结束安全了变成-1. ...
  • 下面交代如何用拓扑排序判断是否有。 我们不妨假设一张图上有n个点。 拓扑排序的核心就是每次找入度为0的点,进入输出队列,然后将与此点相连的节点入度减1,重复做。 重复做的过程中,如果存在结点不...
  • 拓扑排序判断

    2015-05-20 09:39:12
    拓扑排序的实现方法:  (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.  (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.  (3)重复上
  • 拓扑排序 判断是否有

    千次阅读 2011-04-01 14:51:00
          #include #include using namespace std; #define MAX 103 int g[MAX][MAX], n; bool hasCirle(){ int i,j,k;int d[MAX]; memset(d,0,sizeof(d));... d[i]+=g[j]
  • 拓扑排序判断
  • 进行拓扑排序,统计入度为0的点 #include #include #include #include using namespace std ; int main() { int n,m,i,j; while ( cin >>n>>m &&(n+m)) { int mp[ 111 ][ 111 ]={ 0 },in...
  • 判断DAG可以用拓扑排序. 但是枚举边O(m),拓扑排序O(n+m),总复杂度O(m*(n+m)),没办法过. 删除一条边,在拓扑排序中的影响其实只是这条边出点的度数在跑之前减少了1, 那么其实我们枚举度数减少的点就行了. 枚举点的...
  • 题目: 给出几种正方形,每种正方形有无穷多个。在连接的时候正方形可以旋转、翻转。 正方形的每条边上都有一个大写...这个题读完之后,一点思路都没有,看完紫书上的分析知道是用拓扑排序判断有向,但具体的...
  • class Stack: def __init__(self): self.arr = [] def push(self, item): self.arr.append(item) def pop(self): return self.arr.pop(-1) def getTop(self): return self.arr[-1] ... retur
  • 就是拓扑排序判断是否有,有就输出NO,没有就输出YES。 拓扑排序判,用队列实现的话就是看出现在队列中的元素是否跟顶点数相同,如果不同的话肯定是存在的,因为如果最后只剩下,那么并不存在一个入度
  • 很简单,就是通过拓扑排序判断一下关系中是否有就OJBK了 怎么判断是否有呢? 只需要在排序过程中记录一下入度为零的点的个数,要是少于总个数,必成无疑 其实写这篇blog的原因不是为了这道题,而是...
  • vector < int > v [ MAX_N ] ; int n , m , sum [ MAX_N ] ; bool topo ( ) { int num = 0 ; queue < int > q ; //queue,vector,greater<int> >q;...//无 else return false ; }
  • bool dfs (int i)//判断图中是否有的模板 {  vis[i]=-1;//-1表示在当前访问i在递归栈中  for (int j=0;j;j++)  if (theMap[i][j]){  if (vis[j]==-1) return false;//如果i能访问到递归栈中的某个点,...
  • 拓扑排序 题目大意: 两个题一样 有向图判断是否有
  • 所谓拓扑排序,就是对有向图构造拓扑序列的过程。 基本思路:从AOV网中选择一个入度为0的顶点输出,然后删除此顶点,并删除以此顶点为尾的弧,重复此步骤; 直到输出全部顶点或不存在入度为0的顶点为止。 1.数据...
  • 右)判断有无的出现方法:直接拓扑排序,如果能正常排序完,这个就是无的有向图DAG,如果不能,在拓扑排序的过程中有些点的入度经过去边操作之后一直不为零,就是有的存在。csdn的输入体验太糟糕了code将就着看...
  • 执行用时 :20 ms, 在Course Schedule的C++提交中击败了99.80%的用户 内存消耗 :13.2 MB, 在Course Schedule的C++提交中击败了18.08%的用户 ...//拓扑排序 //使用标志数组进行访问判别 //标志数组如果...
  • 拓扑排序判断有向图是否成环

    千次阅读 2018-06-12 19:56:38
    对一个有向图的节点进行拓扑排序,可以用来判断该有向图是否成环,有则无拓扑序列,无则有。 #include &lt;cstdio&gt; #include &lt;cstring&gt; #include&lt;iostream&gt; #include &...
  • 拓扑排序 判断重边

    2020-03-06 11:30:06
    问题 1841: [蓝桥杯][2017年第八届真题]发现 时间限制: 1Sec 内存限制: 128MB 提交: 653 解决: 237 题目描述 小明的实验室有N台电脑,编号1~N。原本这N台电脑之间有N-1条数据链接相连,恰好构成一个树形网络。在树...
  • 注意:当存在冲突或者拓扑排序成功时,之后的输入不对结果造成影响。 思路分析 拿到题第一想法是图论,对小于关系建模然后tarjan求是否有,同时统计出度入度,如果出度=0的点只有一个,入度=0的点也只有一个,就能...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,418
精华内容 4,567
关键字:

拓扑排序判断环