解题思路:拓扑排序
当一个点的入度为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语言代码)浏览:715 |
星期判断机 (C语言代码)浏览:859 |
1054题解浏览:467 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:577 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:518 |
复数求和 (C语言代码)浏览:927 |
C二级辅导-等差数列 (C语言代码)浏览:819 |
筛排处理 (C语言代码)浏览:787 |
1162答案错误,为什么浏览:644 |
马拦过河卒 (C语言代码)浏览:1097 |