bfs的时候用bitset优化一下。
水题
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <bitset> 5 #include <queue> 6 #include <unordered_map> 7 8 using namespace std; 9 10 const int maxn = 1e3+10; 11 int N,M; 12 unordered_map<string,int> mp; 13 14 bitset<maxn> G[maxn]; 15 bitset <maxn> to,unvis; 16 queue <int> Q; 17 18 int dis[maxn]; 19 int bfs(int rt) 20 { 21 while(!Q.empty()) Q.pop(); 22 Q.push(rt); 23 dis[rt] = 0; 24 25 unvis.reset(); 26 for(int i=1;i<=N;i++) unvis.set(i); 27 int res = 0; 28 unvis.reset(rt); 29 30 while(!Q.empty()) 31 { 32 int u = Q.front(); 33 Q.pop(); 34 to = unvis & G[u]; 35 for(int v = to._Find_first(); v<=N; v = to._Find_next(v)) 36 { 37 Q.push(v); 38 unvis.reset(v); 39 dis[v] = dis[u]+1; 40 res = max(res,dis[v]); 41 } 42 } 43 //printf("") 44 if(unvis.any()) return -1; 45 return res; 46 } 47 48 int main() 49 { 50 while(scanf("%d",&N) && N) 51 { 52 mp.clear(); 53 for(int i=0;i<maxn;i++) G[i].reset(); 54 for(int i=1;i<=N;i++) 55 { 56 char tmp[50]; 57 scanf("%s",tmp); 58 mp[tmp] = i; 59 } 60 scanf("%d",&M); 61 for(int i=0;i<M;i++) 62 { 63 char tmp1[50],tmp2[50]; 64 scanf("%s %s",tmp1,tmp2); 65 int u = mp[tmp1],v = mp[tmp2]; 66 //printf("add edge:%d %d ",u,v); 67 G[u].set(v);G[v].set(u); 68 } 69 70 int ans = 0; 71 bool unconnected = 0; 72 for(int i=1;i<=N;i++) 73 { 74 int res = bfs(i); 75 if(res == -1){unconnected = true;break;} 76 ans = max(ans,res); 77 } 78 if(unconnected) printf("-1 "); 79 else printf("%d ",ans); 80 } 81 }