• 执行用时 :20 ms, 在Course Schedule的C++提交中击败了99.80%的用户 内存消耗 :13.2 MB, 在Course Schedule的C++提交中击败了18.08%的用户 ...//拓扑排序 //使用标志数组进行访问判别 //标志数组如果...
执行用时 : 20 ms, 在Course Schedule的C++提交中击败了99.80% 的用户
内存消耗 : 13.2 MB, 在Course Schedule的C++提交中击败了18.08% 的用户
刚好看了刘汝佳老师的算法竞赛上面拓扑部分，想练练手。
这个算法的关键是flag访问数组中，使用了:-1/0/1三个标志

//拓扑排序 //使用标志数组进行访问判别 //标志数组如果是1/0的，则会产生重复遍历的消耗 //如果是-1/0/1的，就可以避免重复计算。  //1：从当前结点开始的拓扑是无环的  //0：还未遍历过 //-1：正在遍历

可以有效防止重复搜索。（flag为1说明从该结点出发已经计算过了）。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//拓扑排序
//使用标志数组进行访问判别
//标志数组如果是1/0的，则会产生重复遍历的消耗
//如果是-1/0/1的，就可以避免重复计算。
//1：从当前结点开始的拓扑是无环的
//0：还未遍历过
//-1：正在遍历
vector<int> flag(numCourses,0);//标志
vector<vector<int> > tmp(numCourses);
if(prerequisites.empty()) return true;
for(int i=0;i<prerequisites.size();i++)
{
tmp[prerequisites[i]].push_back(prerequisites[i]);//对于该课程来说需要修的课
}
bool ans=true;;
for(int i=0;i<numCourses;i++)
{
ans=ans&&dfs(i,flag,tmp);
}
return ans;
}
bool dfs(int i,vector<int> &flag,vector<vector<int> > &tmp)
{
if(flag[i]==-1)//回路.有环
{
return false;
}
if(flag[i]==1)
{
return true;//可以确定从该结点出发没有回路
}
//第一次访问
flag[i]=-1;//正在访问
for(int j=0;j<tmp[i].size();j++)
{
if(dfs(tmp[i][j],flag,tmp))
{
continue;//这个地方没有回路
}
return false;
}
flag[i]=1;//该结点出去的每一个结点都访问完了，没有回路
return true;
}
};
拓展：leetcode 210. 课程表 II 【在课程表 I的基础上加上输出的功能。DFS】

方法二：根据入度判断
课程先后顺序可以理解为一个有向图，有解的条件是此图无环。因此我们可以依据其先后顺序构造有向图，并统计每门课程的入度（即其前一门课程的数量）。
然后将入度为0的所有课程压入栈中，然后将这些课程的下一门课程的入度减1，减完后入度为0则入栈。重复上述操作直到栈为空。 如果最后存在入度不为为0的节点就说明有环，无解。
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int>Indegree(numCourses);/* 统计各个节点的入度 */
vector<vector<int>>graph(numCourses);/* 图的邻接矩阵 */
queue<int>ZeroQ;/* 入度为0的节点的队列 */
vector<int>ans,empty_ans;/* 结果数组 */
int i, j, cnt = 0;
int start, end;//start 依赖于 end, end 是 start 的先修课
for (i = 0; i < prerequisites.size(); ++i) {
start = prerequisites[i];
end = prerequisites[i];
graph[end].push_back(start);
++Indegree[start];//入度加
}
/* 初始化队列 */
for (i = 0; i < numCourses; ++i) {
if (Indegree[i] == 0)
ZeroQ.push(i);
}
while (!ZeroQ.empty()) {
int v = ZeroQ.front();
ans.push_back(v);
ZeroQ.pop();
++cnt;
for (j = 0; j < graph[v].size(); ++j) {
if (--Indegree[graph[v][j]] == 0)
//v 是graph[v][j]这些课程的先修课。v移除代表在拓扑图中把这些先修课移除
ZeroQ.push(graph[v][j]);
}
}
if (cnt != numCourses)
return empty_ans;
return ans;
}
};

展开全文 • //出master数量为0的人 if ( master [ u ] == 0 ) { ++ num ; master [ u ] = - 1 ; flag = false ; for ( int v = 0 ; v < n ; ++ v ) { if ( m [ u ] [ v ] ) -- master [ v ] ; ...
题目
http://acm.hdu.edu.cn/showproblem.php?pid=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
题意
每个人都可以有多个师傅，并且师徒关系是可以传递的，即我师傅的师傅也是我的师傅，我徒弟的徒弟也是我的徒弟 自己的徒弟如果是自己的师傅，输出NO 如果全部合法则输出YES
思路
记录每个人的师傅数量，即每个人的入度. 循环，每次都遍历所有人，将师傅数量为0的结点删除，并减少指向的结点的师傅数量，直到无法再删除任何结点. 如果有环，即自己的徒弟是自己的师傅，则最后会有结点的入度不为0，因为互相是对方的师傅. 所以如果无环，则最后所有人的入度都为0.
代码
#include <cstdio>
#include <cstring>
using namespace std;

bool m;//数据比较少，邻接矩阵方便一点
int master;

int main() {
int n,M,u,v;
while(scanf("%d%d",&n,&M)!=EOF and n) {
memset(master,0,sizeof(master));
memset(m,false,sizeof(m));
while(M--) {
scanf("%d%d",&u,&v);
if(!m[u][v]) {
m[u][v]=true;
++master[v];
}
}

bool flag;
int num=0;//人数
for(;;) {
flag=true;
for(int u=0; u<n; ++u) { //找出master数量为0的人
if(master[u]==0) {
++num;
master[u]=-1;
flag = false;
for(int v=0; v<n; ++v) {
if(m[u][v])
--master[v];
//减去master数量为0的人指向的徒弟的师傅数量
}
}
}
if(flag)break;
}

if(num==n)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}

展开全文 • 【题目】D. Almost Acyclic Graph 【题意】给定n个点的有向图（无重边），问能否删除一条边使得全图无。...拓扑排序后定位到简单：剩余图是+内DAG，DFS过程中将走入死路的点标-1，访问过标...

【题目】D. Almost Acyclic Graph
【题意】给定n个点的有向图（无重边），问能否删除一条边使得全图无环。n<=500,m<=10^5。
【算法】拓扑排序
【题解】找到一个简单环，则欲删除的边一定经过该环。尝试环上的每一条边（至多n条边）后再次拓扑排序判断全图是否有环。
拓扑排序后定位到简单环：剩余图是环+环内DAG，DFS过程中将走入死路的点标-1，访问过标1，找到访问过的点就是简单环。换起始点直到找到环为止。
复杂度O(nm)。  #include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=600,maxm=100010;
struct edge{int v,from;}e[maxm];
int map[maxn][maxn],tot,cnt,n,m,first[maxn],p,vis[maxn],in[maxn],deg[maxn],suc[maxn];
queue<int>Q;
void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;in[v]++;}
void dfs(int x,int fa){
if(p||vis[x]==-1)return;
if(vis[x]==1){p=x;suc[fa]=x;return;}
vis[x]=1;
for(int i=first[x];i;i=e[i].from)if(deg[e[i].v]>0){
dfs(e[i].v,x);
if(p){if(fa&&!suc[p])suc[fa]=x;break;}
}
if(!p)vis[x]=-1;
}
bool solve(int o){
cnt=0;
for(int i=1;i<=n;i++){deg[i]=in[i];if(i==e[o].v)deg[i]--;if(deg[i]==0)Q.push(i),cnt++;}
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=first[x];i;i=e[i].from)if(i!=o&&--deg[e[i].v]==0)Q.push(e[i].v),cnt++;
}
if(cnt==n)return 1;
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
insert(u,v);map[u][v]=tot;
}
cnt=0;
for(int i=1;i<=n;i++){deg[i]=in[i];if(in[i]==0)Q.push(i),cnt++;}
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=first[x];i;i=e[i].from)if(--deg[e[i].v]==0)Q.push(e[i].v),cnt++;
}
if(cnt==n){printf("YES");return 0;}
for(int i=1;i<=n;i++)if(deg[i]>0&&!p)dfs(i,0);
int pp=p;
do{
if(solve(map[p][suc[p]])){printf("YES");return 0;}
p=suc[p];
}while(p!=pp);
printf("NO");
return 0;
}

View Code

另一种解法：枚举点i，in[i]--，拓扑排序找环。这样相当于删除一条指向n的边后全图找环。

转载于:https://www.cnblogs.com/onioncyc/p/8287645.html
展开全文 • Exploration Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 715 Accepted Submission(s): 197 Problem Description ...Miceren like


Exploration
Time Limit: 30000/15000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 715    Accepted Submission(s): 197

Problem Description

Miceren likes exploration and he found a huge labyrinth underground!

This labyrinth has

N
caves and some tunnels connecting some pairs of caves.

There are two types of tunnel, one type of them can be passed in only one direction and the other can be passed in two directions. Tunnels will collapse immediately after Miceren passing them.

Now, Miceren wants to choose a cave as his start point and visit at least one other cave, finally get back to start point.

As his friend, you must help him to determine whether a start point satisfing his request exists.

Input

The first line contains a single integer

T
, indicating the number of test cases.

Each test case begins with three integers

N, M1, M2
, indicating the number of caves, the number of undirectional tunnels, the number of directional tunnels.

The next

M1
lines contain the details of the undirectional tunnels. Each line contains two integers

u, v
meaning that there is a undirectional tunnel between

u, v
. (

u ≠ v
)

The next

M2
lines contain the details of the directional tunnels. Each line contains integers

u, v
meaning that there is a directional tunnel from

u
to

v
. (

u ≠ v
)

T

1 ≤ N,M1,M2 ≤ 1000000.

There may be some tunnels connect the same pair of caves.

The ratio of test cases with

N > 1000
is less than 5%.

Output

For each test queries, print the answer. If Miceren can do that, output "YES", otherwise "NO".

Sample Input

2
5 2 1
1 2
1 2
4 5
4 2 2
1 2
2 3
4 3
4 1

Sample Output

YES
NO

Hint
If you need a larger stack size,

Source

赛码"BestCoder"杯中国大学生程序设计冠军赛

/* ***********************************************
Author        :CKboss
Created Time  :2015年05月07日 星期四 22时48分45秒
File Name     :HDOJ5222.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int maxn=1001000;

int fa[maxn];

int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}

bool Union(int a,int b)
{
a=find(a); b=find(b);
if(a!=b)
{
fa[a]=b; return true;
}
return false;
}

int n,m1,m2;

struct Edge
{
int to,next;
}edge[2*maxn];

int degree[maxn];
bool vis[maxn];

void init()
{
for(int i=0;i<=n+10;i++) fa[i]=i;
memset(degree,0,sizeof(degree));
memset(vis,false,sizeof(vis));
}

{
edge[Size].to=v;
}

int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);

int T_T;
scanf("%d",&T_T);
while(T_T--)
{
scanf("%d%d%d",&n,&m1,&m2);
init();
bool flag=false;
for(int i=0;i<m1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
if(Union(u,v)==false) flag=true;
}

for(int i=0;i<m2;i++)
{
int u,v;
scanf("%d%d",&u,&v);
if(flag) continue;
u=find(u); v=find(v);
if(u!=v)
{
/// u--->v
degree[u]++;
}
else flag=true;
}

if(flag)
{
puts("YES"); continue;
}

queue<int> q;

for(int i=1;i<=n;i++)
{
int u=find(i);
if(vis[u]) continue;
if(degree[u]==0)
{
q.push(u);
vis[u]=true;
}
}

while(!q.empty())
{
int u=q.front(); q.pop();
u=find(u);
{
int v=edge[i].to;
v=find(v);
degree[v]--;
if(degree[v]==0)
{
q.push(v);
vis[v]=true;
}
}
}

bool ck=true;
for(int i=1;i<=n&&ck;i++)
{
if(vis[find(i)]==false) ck=false;
}

if(ck) puts("NO");
else puts("YES");
}

return 0;
}



展开全文 • 拓扑排序过程   在一个有向图中选择一个入度为零的点并且输出,从图(vector建图)中删除这个点和所有以它为尾的边,一直重复上述过程直到不存在没有前驱的顶点。如果此时输出的顶点数小于有向图中的顶点数,说明图中...
• 洛谷里看了几篇都是并查集求，或者Tarjan无脑求什么最大联通分量，额，我都不会，对于的处理只会拓扑排序（感觉最容易理解），网上了个靠谱的拓扑排序的板子，改成最近学的链式前向星存...
• 此题可以一遍拓扑排序求解 即只需要找到一个，就必定存在三元 证明如下： 假设存在一个n元，因为a->b有边，b->a必定没边，反之也成立 所以假设有上三个相邻的点a-> b-> c,那么如果c->a间有边，就已经... c
• 找环有几个问题，首先，是否要求找到...只需对原始的拓扑排序做一些修改即可。 class Solution { map<int, vector<int>> v; public: int dfs(vector<int>& F, vector<int>&path, int
•   这篇文章记录的是另一种用法，就是用有向图来表示任务的依赖关系，然后通过拓扑排序找出按照依赖关系前后顺序完成所有任务的方法。百度里介绍拓扑排序也是说拓扑排序就是这个目的。   就比如说，有 n 个任务...
• 用邻接矩阵实现的拓扑排序，如果不是DAG，会出有向图中的一个（NKU算法作业）
• 题意不难看出是一道简单拓扑题目，自己对于拓扑一直没能掌握。这边就不写思路了，直接上代码了。 我的代码： #include #include #include using namespace std; bool DIS; int r; bool vis; ...
• 题意：给定一个有向图，可以给边染色，若图中存在，则环中所有边不能为同一颜色，求出为了满足条件需要对边染色的最少色数，及染色方案 思路：一个有向图中的边有两种情况...判定有向图是否存在可以用拓扑排序，... Codeforces
• 给定一个有向图，若图无，则将其进行拓扑排序并输出，否则输出IMPOSABLE。 Input 第一行为两个整数n(1 之后m行，每行两个整数a、b表示一条从a到b的有向边。 Output 若存在，输出IMPOSABLE... 排序算法
• 文章目录算法分析拓扑排序模板 算法分析 拓扑排序:把事情看成图的点，把先后关系看成有向边，问题转化为在图中求一个有先后关系的排序，就是拓扑排序拓扑排序用BFS和DFS均可实现。 如何排序? 拓扑排序需要根据点... 队列 算法
• 分析：首先对于成环的问题就按照常规的拓扑排序判断有向的操作来搞，不赘述。然后这个判断层次，这两天脑子 一糊把题看错了，把关系搞反了，wa到怀疑人生。思路大概这样：拿一个变量cur记录当前层次
• 拓扑排序来做，点之间相连形成了一个有向图，题目就是来判断这个有向图里面是否有，如果有则不合法。方法是每次入度为0的点，如果找到，入度减1，与之相连的点也相应-1，如果没找到，那么则说明有向图里面存在...
• 拓扑序列是有向无图按拓扑排序生产的序列，（有向无图一定有拓扑序，反之一定没有拓扑序），对于有向无图，一定存在一个入度为 0 的点，该点是拓扑序的第一个点，将该点拿出，并将于该点相连的点的入度全部减... 队列 算法
• 题意：给你一个n个点m条边的有向图，每一个顶点都对应一个字母，定义一条路径的价值为：从一个顶点开始这...分析： 拓扑排序 + dp 拓扑排序 ： 　由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到 树状dp dfs
• 在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到...拓扑排序是对有向无图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。DAG在区块链中得到很广泛的应用哦。 数据结构
• Mr. Kitayuta's Technology CodeForces - 505D（并查集+拓扑排序或dfs找环） 题解 并查集 dfs
• 拓扑排序是对一个有向无图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。0.1) 本文总结于 数据结构...  ...