解题思路:拓扑排序
当一个点的入度为0时候,那么此刻她是当前女友。
注意事项:因为是多组测试数据,因此需要处理好初始化的工作,否则容易出现部分正确的情况。
参考代码:
#include<iostream> #include<algorithm> #include<map> #include<cstring> #include<string> #include<vector> #include<set> #include<queue> using namespace std; int cnt,InNum[110],res[110],vis[110]; vector<int>Next[110]; map<string,int>mp; map<int,string>names; int num(string name) { if(mp.find(name)==mp.end()) { mp[name]=++cnt; names[cnt]=name; } return mp[name]; } /* void dfs(int pre,int dep,int*res,int &ok) { if(ok==true) return ; for(set<int>::iterator it=next[pre].begin();it!=next[pre].end();it++)//寻找 { int u = *it; if(!vis[u]) { int flag = true; for(int k=1;k<=dep-1;k++) { int p=res[k]; if(prex[p].find(u)!=prex[p].end()) { flag=false; break; } } if(flag==false) continue; vis[u]=true; res[dep]=u; if(dep==cnt) { ok=true; for(int i=1;i<=cnt;i++) { cout<<names[i]; if(i!=cnt) cout<<" "; } } else { dfs(u,dep+1,res,ok); } vis[u]=false; } } } */ int main(void) { //freopen("D:\\input1.txt","r",stdin); int T,n; cin>>T; while(T--) { //初始化 cnt=0; mp.clear(); names.clear(); for(int i=0;i<110;i++) Next[i].clear(); memset(vis,0,sizeof(vis)); memset(InNum,0,sizeof(InNum)); cin>>n; for(int i=1;i<=n;i++) { string name1,name2; cin>>name1>>name2; int num1=num(name1); int num2=num(name2); Next[num1].push_back(num2); InNum[num2]++;//入度加一 } queue<int>Q; for(int i=1;i<=cnt;i++) if(InNum[i]==0) { vis[i]=true; Q.push(i); } int count=0; while(!Q.empty()) { count++; int t = Q.front(); Q.pop(); res[count]=t; for(int i=0;i<Next[t].size();i++) { int p = Next[t][i]; InNum[p]--; } for(int i=1;i<=cnt;i++) if(InNum[i]==0 && vis[i]==false) { vis[i]=true; Q.push(i); } } for(int i=1;i<=cnt;i++) { cout<<names[res[i]]; if(i!=cnt) cout<<" "; } if(T) cout<<endl; } return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题6.2 (C++代码)为什么回车不算字符浏览:1185 |
C语言程序设计教程(第三版)课后习题8.9 (C++代码)浏览:844 |
2004年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:681 |
C语言考试练习题_排列 (C++代码)浏览:628 |
C二级辅导-公约公倍 (C语言代码)浏览:1508 |
C语言训练-计算一个整数N的阶乘 (C语言代码)浏览:928 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:530 |
十->二进制转换 (C语言代码)浏览:1291 |
ASCII帮了大忙浏览:748 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:660 |