USTC机试—拓扑排序加强版

如题所示:

//算法求解:求拓扑排序的问题
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<stack>
using namespace std;
#define N 100
vector<int> E[N];//N个节点打头的邻接表
int degree[N];
int main(){
	FILE *fp1,*fp2;
	stack<int> q;
	fp1=fopen("3.in","r");
	fp2=fopen("3.out","w");
	int count=0;//统计总任务数
	for(int i=0;i<N;i++){degree[i]=0;//初始化所有节点的度数均是0
	 E[i].clear();//清空邻接链表*****遗漏点
	}
	while(!q.empty())q.pop();//清空栈中的信息****遗漏点
	while(!feof(fp1)){
	   char s[N];
	   int k=0;
	   fgets(s,99,fp1);
	   int sign=1;
	   int temp;
	   while(s[k]!='\0'){//将顶点信息输入邻接表中,同时更新度数
		   if(s[k]>='0'&&s[k]<='9'&&sign==1){
		       temp=s[k]-'0';
			   sign=0;
			   count++;
			   k++;
		   }
		   else if(s[k]>='0'&&s[k]<='9'&&sign==0){
			   int h=s[k]-'0';
		       E[temp].push_back(h);//***错误点
			   degree[h]++;//h结点入度加一
			   k++;
		   }
           else{k++;}
	   }
	}
	for(i=0;i<count;i++){
	   if(degree[i]==0)q.push(i);
	}
	while(!q.empty()){
	    int m=q.top();
		fprintf(fp2,"Task%d ",m);
		q.pop();
		for(i=0;i<E[m].size();i++){//注:vector是用size+for循环并不能用empty因为其无pop函数
		    degree[E[m][i]]--;
			if(degree[E[m][i]]==0)q.push(E[m][i]);
		}
	}
 return 0;
}


全部评论

相关推荐

不愿透露姓名的神秘牛友
06-27 15:07
点赞 评论 收藏
分享
见见123:简历没有啥问题,是这个社会有问题。因为你刚毕业,没有工作经历,现在企业都不要没有工作经历的。社会病了。
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务