1003. Erdős Number

发布时间:2014-10-22 12:59:41编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"1003. Erdős Number",主要涉及到1003. Erdős Number方面的内容,对于1003. Erdős Number感兴趣的同学可以参考一下。

  Time Limit: 1sec    Memory Limit:256MB Description The  Erdős  number describes the "collaborative distance" between a person and mathematician Paul Erdős. To be assigned an Erdős number, an author must co-write a research paper with an author with a finite Erdős number. Paul Erdős has an Erdős number of zero. Anybody else's Erdős number is k + 1 where k is the lowest Erdős number of any coauthor. Erdős wrote around 1,500 mathematical articles in his lifetime, mostly co-written. He had 511 direct collaborators; these are the people with Erdős number 1. The people who have collaborated with them (but not with Erdős himself) have an Erdős number of 2, those who have collaborated with people who have an Erdős number of 2 (but not with Erdős or anyone with an Erdős number of 1) have an Erdős number of 3, and so forth. (from wikipedia.org).     Input Assume that Paul Erdős is numbered 0, other actors are numbered by positive integers between 1 to 100. The first line is the number of test cases. Each test case start with the number m of actors in a line, then m pairs of authors are followed. Output For each test case, each author's  Erdős number is printed out, if it is finite,  in a separate line in the form "author number: Erdősnumber" in the order of increasing actor number, and finally  a dotted line "---" is printed out in a separate line. Sample Input  Copy sample input to clipboard 2 1 0 1 3 0 4 0 2 2 3 Sample Output 1:1 --- 2:1 3:2 4:1 --- 题目的意思是输出到0这点的距离,利用广度优先搜索,结果是我在代码上的处理有些问题,标记顺序的问题,真是不应该这样写。 直接上代码吧// Problem#: 8592 // Submission#: 2196678 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ // All Copyright reserved by Informatic Lab of Sun Yat-sen University #include<iostream> #include<queue> #include<memory.h> using namespace std; queue<int>qu; int id[105]; bool visit[105]; bool adj[105][105]; int countt; void bfs() { while(!qu.empty()) { int tmp=qu.front(); //visit[tmp]=true;这里不能标记,一直是WA,因为考虑到一个顺序的问题 for(int i=0;i<105;i++) { if(adj[tmp][i]&&!visit[i]) { visit[i]=true;//进入队列就标记为访问过 id[i]=id[tmp]+1; qu.push(i); } } qu.pop(); } } int main() { int casen; cin>>casen; while(casen--) { while(!qu.empty()) qu.pop(); memset(adj,false,sizeof(adj)); memset(visit,false,sizeof(visit)); int m; cin>>m; int temp=m; while(m--) { int a,b; cin>>a>>b; adj[a][b]=true; adj[b][a]=true; } memset(id,-1,sizeof(id)); id[0]=0; visit[0]=1; qu.push(0); bfs(); for (int i = 1; i < 105; ++i) { /* code */ if(id[i]!=-1) cout<<i<<":"<<id[i]<<endl; } cout<<"---"<<endl; } }

上一篇:SVM支持向量机(Support Vector Machine)-翻译版
下一篇:Linux awk