首页 > 代码库 > POJ1128-DAG拓扑排序
POJ1128-DAG拓扑排序
题目链接POJ1128
思路
如果在A的边框上出现了字母B,就说明B在A的上方
如果边框A在边框B的下方,就添加从A到B的一条有向边(题目要求从下到上输出)
那么所求的是所得有向无环图的拓扑排序
题目还要求按照字典序输出所有可能的顺序,用深度优先搜索
附代码
#include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <iostream> #include <algorithm> #define MAX 1000007 #define MAXN 50 #define MAXM 1007 #define INF 0x3f3f3f3f #define NINF 0xc0c0c0c0 #define MOD 1000000007 using namespace std; typedef long long LL; int head[MAXN],tot,n,m,indegree[MAXN],realn; struct Edge{ int to; int next; }edge[MAXM]; void addEdge(int u,int v){ edge[tot].to=v; indegree[v]++; edge[tot].next=head[u]; head[u]=tot++; } int visit[MAXN],Map[40][40],flag[40][40],df[MAXN]; struct Border{ int x1,y1,x2,y2; }border[MAXN]; int Queue[MAXN],iq; void init(){ tot=iq=realn=0; memset(head,-1,sizeof head); memset(visit,0,sizeof visit); memset(Map,0,sizeof Map); memset(flag,0,sizeof flag); memset(indegree,0,sizeof indegree); memset(df,0,sizeof df); for(int i=0;i<MAXN;i++){ border[i].x1=border[i].y1=40; border[i].x2=border[i].y2=-1; } } //如果字母t在字母k的四条边框上,则连接k到t的有向边(从下到上的方向) void addE(int k,int x1,int y1,int x2,int y2){ for(int i=x1;i<=x2;i++){ for(int j=y1;j<=y2;j++){ int t=Map[i][j]; if(k!=t && !flag[k][t]){ flag[k][t]=1; addEdge(k,t); } } } } //深度优先遍历出所有的拓扑排序 void dfs(int now,int k){ //cout<<now<<" "<<k<<endl; if(k==realn){ for(int i=1;i<=realn;i++){ printf("%c", Queue[i]+‘A‘-1); } printf("\n"); } else{ //删掉与now关联的边 for(int i=head[now];i!=-1;i=edge[i].next){ indegree[edge[i].to]--; } //从剩余的点中选择入度为0的点,从小到大遍历 for(int i=1;i<MAXN;i++){ if(!df[i]&&visit[i]&&indegree[i]==0){ df[i]=1; Queue[k+1]=i; dfs(i,k+1); df[i]=0; } } //加回与now关联的边 for(int i=head[now];i!=-1;i=edge[i].next){ indegree[edge[i].to]++; } } } int main(){ char ch; while(scanf("%d%d",&n,&m)==2){ init(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf(" %c",&ch); if(ch!=‘.‘){ Map[i][j]=ch-‘A‘+1; } } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int t=Map[i][j]; if(t){ visit[t]=1; border[t].x1=min(border[t].x1,i); border[t].y1=min(border[t].y1,j); border[t].x2=max(border[t].x2,i); border[t].y2=max(border[t].y2,j); } } } for(int k=1;k<30;k++){ if(visit[k]){ addE(k,border[k].x1,border[k].y1,border[k].x1,border[k].y2); addE(k,border[k].x2,border[k].y1,border[k].x2,border[k].y2); addE(k,border[k].x1,border[k].y1,border[k].x2,border[k].y1); addE(k,border[k].x1,border[k].y2,border[k].x2,border[k].y2); } } //cout<<tot<<endl; for(int i=1;i<=30;i++){ if(visit[i]){ realn++; addEdge(0,i); } } //cout<<realn<<endl; dfs(0,0); } return 0; } /* 6 6 BBBCCC BAAAAC BABCAC .ADDA. .AAAA. ..DD.. */
POJ1128-DAG拓扑排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。