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

    千次阅读 2011-04-01 14:51:00
    //圈 d[i]=-1; for(j=0;j;++j) d[j]-=g[i][j]; } return false;//无圈 } void init(){ int i,j; for(i=0;i;++i){ for(j=0;j;++j) cin>>g[i][j]; } } int main(int argc, char *argv[]) {...

     

     

     

    展开全文
  • 下面交代如何用拓扑排序判断是否有环。 我们不妨假设一张图上n个点。 拓扑排序的核心就是每次找入度为0的点,进入输出队列,然后将与此点相连的节点入度减1,重复做。 重复做的过程中,如果存在结点不...

    2019年3月2日

    经典例题,任务调度的合理性。

    例题:http://blog.csdn.net/u012860063/article/details/41170183

    #include<bits/stdc++.h>
    #define inf 0x3f3f3f
    #define maxn 10010
    using namespace std;
    typedef long long ll;
    vector<int> e[maxn];
    queue<int> que;
    int inDegree[maxn],ans,m,n;
    
    void topo(){
        ans=0;
        while(!que.empty()) que.pop();
        for(int i=1;i<=n;i++){
            if(inDegree[i]==0) {que.push(i);}
        }
        while(!que.empty()){
            int q1,q2,q3;
            q1=que.front();
            que.pop();
            ans++;
            for(int j=0;j<e[q1].size();j++){
                inDegree[e[q1][j]]--;
                if(!inDegree[e[q1][j]]){
                    que.push(e[q1][j]);
                }
            }
        }
        //cout<<ans<<" "<<n<<endl;
        if(ans==n) cout<<"1"<<endl;
        else cout<<"0"<<endl;
    }
    int main(){
        std::ios::sync_with_stdio(false);
        while(cin>>n){
            for(int i=0;i<=n;i++){
                e[i].clear();
                inDegree[i]=0;
            }
            for(int i=1;i<=n;i++){
                cin>>m;
                for(int j=1;j<=m;j++){
                    int x;
                    cin>>x;
                    e[x].push_back(i);
                    inDegree[i]++;
                }
            }
            topo();
        }
        return 0;
    }
    
    

    首先,拓扑排序只在有向无环图中成立。下面交代如何用拓扑排序判断是否有环。

    我们不妨假设一张图上有n个点。
    拓扑排序的核心就是每次找入度为0的点,进入输出队列,然后将与此点相连的节点入度减1,重复做。
    重复做的过程中,如果存在结点不能被删除,证明存在环。

    例题:http://blog.csdn.net/u012860063/article/details/41170183

    //拓扑排序判断是否存在环
    #include<iostream>
    #define maxn 510
    using namespace std;
    int G[maxn][maxn];      //记录路径
    int in_degree[maxn];    //记录入度
    int ans[maxn];
    int n,m,x,y;
    int i,j;
    int flag=0;
    
    void toposort(){
        flag=0;
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                if(G[i][j])
                    in_degree[j]++;
            }
        }
        
        for(i=1;i<=n;i++){  //从最小的开始找
            //这样保证有多个答案时候序号小的先输出
            int k=1;
            while(!in_degree[k]){   //寻找入度为0的点
                k++;
                if(k>n){
                    flag=1;
                    break;
                }
            }
            
            ans[i]=k;
            in_degree[k]=-1;
            //更新为-1,后面检测补受影响,相当于删除结点
            for(int j=1;j<=n;j++){
                if(G[k][j]){
                    in_degree[j]--;  //相连的入度减1
                }
            }
        }
    }
    
    int main(){
        while(cin>>n){
            memset(in_degree,0,sizeof(in_degree));
            memset(ans,0,sizeof(ans));
            memset(G,0,sizeof(G));
            
            for(i=1;i<=n;i++){
                cin>>m;
                for(j=0;j<m;j++){
                    cin>>y;
                    G[i][y]=1;
                }
            }
            
            toposort();
            if(flag)
                cout<<"0"<<endl;
            else
                cout<<"1"<<endl;
        }
        return 0;
    }
    
    
    展开全文
  • dfs解拓扑排序在无情况下很方便,反向存边然后dfs即可。但要判断有没有时,需要用回溯的思路:对每个点dfs,若无,回溯时将这个点视为安全。具体操作时,存一个flag,dfs进入时让它为1,结束安全了变成-1. ...

    解法一:dfs回溯法
    dfs解拓扑排序在无环情况下很方便,反向存边然后dfs即可。但要判断有没有环时,需要用回溯的思路:对每个点dfs,若无环,回溯时将这个点视为安全。具体操作时,存一个flag,dfs进入时让它为1,结束安全了变成-1.

    class Solution {
    map<int, vector<int>> m;
    map<int, int> F;
    public:
        int dfs(int n)
        {
            if(F[n] == -1)return true;
            if(F[n] == 1)return false;
            F[n] = 1;
            for(auto node: m[n])
            {
                int ok = dfs(node);
                if(!ok)return 0;
            }
            F[n] = -1;
            return 1;
        }
    
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
            for(int i=0;i<prerequisites.size();i++)
            {
                int a = prerequisites[i][0], b = prerequisites[i][1];
                m[a].push_back(b);
            }
    
            for(int i=0;i<numCourses;i++)
            {
                int ok = dfs(i);
                if(!ok)return false;
            }
    
            return true;
        }
    };
    

    解法二:bfs
    记录每个点的入度,每次选取入度为0的,就可以直接选取。选取后把指向的元素入度-1即可。如果没选完,但是入度没有为0的点了,说明存在环(可以思考一下)。

    class Solution {
    map<int, vector<int>> m;
    public:
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
            int n = numCourses;
            int indegrees[n];
            memset(indegrees, 0, sizeof(indegrees));
            for(int i=0;i<prerequisites.size();i++)
            {
                int a = prerequisites[i][0], b = prerequisites[i][1];
                indegrees[a] += 1;
                m[b].push_back(a);
            }
    
            queue<int> zeros;
            int remains = n;
            for(int i=0;i<n;i++)
            {
                if(indegrees[i] == 0)zeros.push(i);
            }
    
            while(!zeros.empty() && remains > 0)
            {
                int a = zeros.front();
                zeros.pop();
                remains--;
                for(int i=0;i<m[a].size();i++)
                {
                    indegrees[m[a][i]]--;
                    if(indegrees[m[a][i]] == 0)zeros.push(m[a][i]);
                }
            }
    
            if(remains > 0)return false;
            else return true;
        }
    };
    
    展开全文
  • n个人为师傅徒弟关系,但是既当师傅又当徒弟是非法的,给了你m组关系,让发你判断是否合法,就是判断是否有环: 思路: 进行拓扑排序,统计入度为0的点 #include #include #include #include using ...

    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 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
    Source
    HDOJ Monthly Contest – 2010.03.06

    题意:
    n个人为师傅徒弟关系,但是既当师傅又当徒弟是非法的,给了你m组关系,让发你判断是否合法,就是判断是否有环:
    思路:
    进行拓扑排序,统计入度为0的点

    #include<iostream>
    #include<cstdio>
    #include<queue>
    #include<vector>
    using namespace std;
    int main()
    {
        int n,m,i,j;
        while(cin>>n>>m &&(n+m))
        {
            int mp[111][111]={0},in[111]={0};
            while(m--)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                mp[a][b]=1;
            }
            for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                if(mp[i][j]) in[j]++;
            priority_queue<int ,vector<int>,greater<int> > q,p;
            for(i=0;i<n;i++)
                if(!in[i])
                    q.push(i);
          //  cout<<q.top()<<"(("<<endl;
            while(!q.empty())
            {
                int v=q.top();
                q.pop();
                p.push(v);
                for(i=0;i<n;i++)
                {
                    if(!mp[v][i]) continue;
                    in[i]--;
                    if(!in[i])
                        q.push(i);
                }
            }
            int cnt=p.size();
            if(cnt==n)
                puts("YES");
            else puts("NO");
        }
        return 0;
    }
    
    展开全文
  • 很简单,就是通过拓扑排序判断一下关系中是否有环就OJBK了 怎么判断是否有环呢? 只需要在排序过程中记录一下入度为零的点的个数,要是少于总个数,必成无疑 其实写这篇blog的原因不是为了这道题,而是...
  • 题目大意 题目链接 好像就是先告诉你他要用26个字母的前n个字母,然后给你m...拿到题第一想法是图论,对小于关系建模然后tarjan求是否有环,同时统计出度入度,如果出度=0的点只有一个,入度=0的点也只有一个,就能...
  • AOV网,判断网中是否存在 否则打印出拓扑序列
  • 题目: 给出几种正方形,每种正方形无穷多个。在连接的时候正方形可以旋转、翻转。 正方形的每条边上都一个大写...这个题读完之后,一点思路都没有,看完紫书上的分析知道是用拓扑排序判断有,但具体的...
  • 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
  • 拓扑排序判断环

    2018-06-14 23:35:23
    给你一个N点和M条向边的图,问你该图是否拓扑排序.#include&lt;cstdio&gt; #include&lt;cstring&gt; #include&lt;vector&gt; #include&lt;queue&gt; using namespace std; ...
  • 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能访问到递归栈中的某个点,...
  • 题意:给定n种正方形,每种正方形的数量可视为无数个,正方形的每条边都标号,正方形可进行旋转和翻转,对于两条边A+可与A-连接在一起,B+可与B-连接在一起,以此类推,00不能与任何边连接。问是否存在一种连接...
  • 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 ; }
  • 今天我们来聊聊向图中环的判断,在数据结构中我们知道,通过拓扑排序可以判断有向图中是否存在,对于向图的存储我们采用邻接表的形势,这里为了简化链表的操作,我们省略了链表,避免了指针的麻烦,直接采用了...
  • 拓扑排序判断有的题目,对于判的题,判无向一般用并查集,判一般用拓扑排序 #include <bits/stdc++.h> using namespace std; int main(){ int v,e,in[105],x,y; vector<int> adjl...
  • 题目连接: ...本体 阶梯大意:《1》用map对字符串进行编号《2》用拓扑排序 进行判断是否存在 代码如下: #include #include #include #include #include #include #include using namespace std
  • Java 判断有向图是否有环 拓扑排序

    千次阅读 2020-03-13 22:32:27
    拓扑排序 import java.util.*; public class Demo1{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); while (sc.hasNext()){ int point=Inte...
  • 题目链接:http://poj.org/problem?id=1094题意:...2.是否有环 3.没有唯一解注意1,3还要输出在第几个关系可以判断出来,可知3需要判断到最后,而1可能不需要。AC代码:#include #include #include #include <cstd
  • 数据结构AOE网 和AOV-网一节 意义就是: 给出一些事件和活动 (图),该事件进行的前提条件是,所有以该事件... 可以得到一个拓扑序列,并且还可以计算对应事件或者边的最早发生事件和最晚发生时间。 代码实现:...
  • DAG图:向无拓扑排序:只有DAG图才能成功实现拓扑排序此算法将判断此图是否为DAG图,如果是DAG图,则输出其中一种拓扑序列代码如下:#include"stdafx.h" #include&lt;cstdio&gt; #include&...
  • 我们直接先把所有的向边建图,然后拓扑排序判断环,如果此时环那么直接输出no 为了将无向边变成向边之后依旧无环,那么我们只需要遵循拓扑排序的规则,给无向图指定方向的时候对于每条边,从拓扑序小的点指向...
  • 拓扑排序+判断图中是否有环 拓扑排序:从一个顶点开始,进行dfs,直到某一个点再也没有出度,没有出度的点可以认为是最大的点(之一)。 是否有环:为visited数组多添加一个状态:正在被访问状态。如果在一次递归中...
  • 拓扑排序判断有向图是否成环

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

空空如也

空空如也

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

拓扑排序判断是否有环