图论题:一开始我是用tarjan算法做的,wrong answer 了很多次,然后又用了floyd-warshell算法,也wa了
最后找了题解,原来最后的dataset后面不是组数,是样例的编号,题根本就没说,让人怎么理解。。。
tarjan
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<map> #include<algorithm> #define M 100 using namespace std; int qis; int maps[50][50]; int dfn[M],low[M],vis[M],stacks[M]; int belongs[25][50]; int cnt ,scnt,begin,ans; void init(){ memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(stacks,0,sizeof(stacks)); memset(vis,0,sizeof(vis)); memset(belongs,0,sizeof(belongs)); memset(maps,0,sizeof(maps)); qis = cnt = scnt = begin = ans =0; } void tarjan(int x){ int v; dfn[x] = low [x] = ++cnt ; stacks[++begin] = x; for(int i = 1;i<=qis;i++){ if(maps[x][i]){ if(!dfn[i]){ tarjan(i); low[x] = min(low[x],low[i]); } else if(!vis[i]){ low[x] = min(low[x],dfn[i]); } } } if(low[x] == dfn[x]){ scnt ++; do{ v = stacks[begin--]; belongs[scnt][++belongs[scnt][0]] = v;//顶点处理 vis[v] = 1; }while(v != x); if(belongs[scnt][0]>1)ans ++; } } int main(){ int flag = 1; int n,m; int cases = 1; while(scanf("%d%d",&n,&m),n||m){ string a,b; init(); map<string,int>ms; map<int,string>_ms; ms.clear();_ms.clear(); for(int i = 0;i<m;i++){ cin>>a>>b; if(ms[a] == 0)ms[a] = ++qis; if(ms[b] == 0)ms[b] = ++qis; _ms[ms[a]] = a; _ms[ms[b]] = b; maps[ms[a]][ms[b]] = 1; } for(int i =1;i<= qis;i++){ if(!dfn[i])tarjan(i); } if(flag == 1)flag = 0; else puts(""); printf("Calling circles for data set %d:\n",cases++); for(int i = 1;i<=scnt;i++){ int j; for(j = 1;j<belongs[i][0];j++) cout<<_ms[belongs[i][j]]<<", "; cout<<_ms[belongs[i][j]]<<endl; } } }
floyd-warshell:
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<map> #include<algorithm> #define M 100 using namespace std; int qis; int maps[50][50]; int vis[M]; int belongs[25][50]; int scnt ,ans; int cases = 1; int main(){ int flag = 1; int n,m; while(scanf("%d%d",&n,&m),n||m){ qis =ans = scnt = 0; string a,b; map<string,int>ms; map<int,string>_ms; ms.clear();_ms.clear(); memset(vis,0,sizeof(vis)); memset(maps,0,sizeof(maps)); memset(belongs,0,sizeof(belongs)); for(int i = 1;i<=n;i++)maps[i][i] = 1; for(int i = 0;i<m;i++){ cin>>a>>b; if(ms[a] == 0)ms[a] = ++qis; if(ms[b] == 0)ms[b] = ++qis; _ms[ms[a]] = a; _ms[ms[b]] = b; maps[ms[a]][ms[b]] = 1; } //floyd for(int k = 1;k <= n;k++) for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++){ maps[i][j] = maps[i][j] || (maps[i][k] && maps[k][j]); } for(int i = 1;i<=n;i++){ if(vis[i] == 0){ scnt++; for(int j = 1;j<=n;j++){ if(maps[i][j]&&maps[j][i]){ belongs[scnt][++belongs[scnt][0]] = j; vis[j] = 1; } } if(belongs[scnt][0]>1)ans++; } } if(flag == 1)flag = 0; else puts(""); printf("Calling circles for data set %d:\n",cases++); for(int i = 1;i<=scnt;i++){ int j; for(j = 1;j<belongs[i][0];j++) cout<<_ms[belongs[i][j]]<<", "; cout<<_ms[belongs[i][j]]<<endl; } } }