做网站公司长沙,个人注册企业查询,网站访问统计方案,wordpress主题给定一个 n
个点 m 条边的有向图#xff0c;点的编号是 1 到 n
#xff0c;图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列#xff0c;如果拓扑序列不存在#xff0c;则输出 −1
。
若一个由图中所有点构成的序列 A
满足#xff1a;对于图中的每条边 (…给定一个 n
个点 m 条边的有向图点的编号是 1 到 n
图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列如果拓扑序列不存在则输出 −1
。
若一个由图中所有点构成的序列 A
满足对于图中的每条边 (x,y)x 在 A 中都出现在 y 之前则称 A
是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n
和 m
。
接下来 m
行每行包含两个整数 x 和 y表示存在一条从点 x 到点 y 的有向边 (x,y)
。
输出格式
共一行如果存在拓扑序列则输出任意一个合法的拓扑序列即可。
否则输出 −1
。
数据范围
1≤n,m≤105 输入样例
3 3
1 2
2 3
1 3输出样例
1 2 3基于BFS的拓扑序列
#include iostream
#include cstring
#include algorithmusing namespace std;const int N100010,M100010;
int n,m;
struct Node
{int id;Node* next;Node(int _id):id(_id),next(NULL){}
}*head[N];int d[N],q[N]; //用数组d表示入度 //用数组模拟队列void add(int a,int b){ //邻接表存储auto pnew Node(b); //头插法p-nexthead[a];head[a]p;
}
bool topsort(){int hh0,tt-1; //队列的队头队尾for(int i1;in;i){if(!d[i]) //如果入度为0入队q[tt]i;}while(hhtt){int tq[hh]; //取队头for(auto phead[t];p;pp-next){ //枚举p的所有邻边if(--d[p-id]0) q[tt]p-id; //如果邻边的入度为0邻边入队}}return ttn-1;
}
int main()
{scanf(%d%d, n, m);while(m--){int a,b;scanf(%d%d, a, b);d[b]; add(a, b); //邻接表存储a的邻边}if(!topsort()) puts(-1); //如果没有拓扑排序else{ //输出其中一条路径for(int i0;in;i)printf(%d ,q[i]); }
}
基于DFS的拓扑序列
#include iostream
#include cstring
#include algorithm
using namespace std;int n,m;
const int N100010;
int st[N],q[N],top;struct Node
{int id;Node* next;Node(int _id):id(_id),next(NULL){}
}*head[N];
void add(int a,int b) //邻接表头插法
{auto pnew Node(b); p-nexthead[a];head[a]p;
}
bool dfs(int a)
{st[a]1; //遍历过在递归中for(auto phead[a];p;pp-next) //取邻接表的头{int jp-id;if(!st[j]) {if(!dfs(j)) return false; //如果发现有环}else if(st[j]1){ //如果在递归中return false;}}q[top]a; //注意是否是拓扑排序的逆序st[a]2;return true;
}
bool topsort()
{for(int i1;in;i)if(!st[i] !dfs(i)) //如果搜过,有环return false;return true;
}int main()
{scanf(%d%d, n, m);while(m--){int a,b;scanf(%d%d, a, b);add(a, b);}if(!topsort()) puts(-1);else{for(int in-1;i0;i--)printf(%d ,q[i]);}return 0;
}
