bfs（23分，case3无法通过。经查是bfs结构写错）：
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map> #define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 10010 #define MAX 0x06FFFFFF #define V vector<int> using namespace std; int n; vector<int> g[LEN]; int vis[LEN]; int deep=0; set<int> ans; int block=0; int main(){ // freopen("D:\CbWorkspace\PAT\图的遍历 1021_1.txt","r",stdin); int a,b,i,j,k; I("%d",&n); FF(i,n-1){ I("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); } for(i=1;i<=n;i++) if(!vis[i]){ queue<int> q; q.push(i); int d=0; int cnt=1; while(!q.empty()){ d++; int s=q.size(); FF(j,s){ int t=q.front(); q.pop(); // if(vis[t]) continue; FF(k,g[t].size()){ int tmp=g[t][k]; if(vis[tmp]) continue; cnt++; q.push(tmp); vis[tmp]=1; } } } if(cnt>=n){ if(d>deep){ ans.clear(); deep=d; ans.insert(i); }else if(d==deep){ ans.insert(i); } memset(vis,0,sizeof vis); }else{ block++; } } if(block>1){ printf("Error: %d components ",block); }else{ set<int>::iterator it=ans.begin(); while(it!=ans.end()){ printf("%d ",*it); it++; } } return 0; }
AC代码：
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map> #define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 10010 #define MAX 0x06FFFFFF #define V vector<int> using namespace std; int n; vector<int> g[LEN]; int vis[LEN]; int deep=0; set<int> ans; int block=0; int main(){ // freopen("D:\CbWorkspace\PAT\图的遍历\1021_2.txt","r",stdin); int a,b,i,j,k; I("%d",&n); FF(i,n-1){ I("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); } for(i=1;i<=n;i++) if(!vis[i]){ queue<int> q; q.push(i); int d=0; int cnt=1; while(!q.empty()){ d++; int sz=q.size(); while(sz-->0){ int t=q.front(); q.pop(); vis[t]=1; FF(k,g[t].size()){ int tmp=g[t][k]; if(vis[tmp]==0){ cnt++; q.push(tmp); vis[tmp]=1; } } } } if(cnt>=n){ if(d>deep){ ans.clear(); deep=d; ans.insert(i); }else if(d==deep){ ans.insert(i); } memset(vis,0,sizeof vis); }else{ block++; } } if(block>1){ printf("Error: %d components ",block); }else{ set<int>::iterator it=ans.begin(); while(it!=ans.end()){ printf("%d ",*it); it++; } } return 0; }
注意正确的BFS结构：
queue<int> q; //建立队列 q.push(i); //入队 while(!q.empty()){ //非空判断 int sz=q.size(); while(sz-->0){ //当前层 int t=q.front(); //出队 q.pop(); vis[t]=1; //出队已访问 FF(k,g[t].size()){ //出队顶点的所有后继 int tmp=g[t][k]; if(vis[tmp]==0){ //这个后继未访问 q.push(tmp); //入队 vis[tmp]=1; //入队已访问 } } } }
并查集+dfs: