几经周折一直WA。用AC的代码测试了不同的输入输出,和自己代码的运行结果一致。 因为看不了WA的输入输出,所以确实是不知道原因了。 跪求大牛指点一下迷津Orz。 下附代码:
#include<bits/stdc++.h>
using namespace std;
#define N 40
int n,m,T,sum;
int circle[N][N],used[N];
string name1,name2;
string caller[N];
map<string,int>mp;
//将mp中对应名字的电话组更新,并用callCircle数组保存名字
void mapping(string name){
if(!mp[name]){
sum++;
mp[name]=sum;
caller[sum]=name;
}
}
//Floyd算法,用于检测连通性,基本思想就是以k中间点,遍历整个call二维数组,然后若k与两者都连通,则此两者连通,更新数组
void Floyd(int n){
for(int k=1;k<n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
circle[i][j]=circle[i][j]||(circle[i][k]&&circle[k][j]);//与运算,两者为1,即皆与k结点连通则i,j两者连通
}
int main()
{
while(++T)
{
//初始化
sum=0;
//输入
cin>>n>>m;
if(!n&&!m) break;
//初始化
memset(circle,0,sizeof(circle));
memset(used,0,sizeof(used));
mp.clear();
//依据电话记录映射map
for(int i=1;i<=m;i++){
cin>>name1>>name2;
mapping(name1);
mapping(name2);
circle[mp[name1]][mp[name2]]=1; //更新连通性
}
//用Floyd算法测连通性,即求电话圈
Floyd(n);
//输出
cout<<"Calling circles for data set "<<T<<":"<<endl;
for(int i=1;i<=n;i++){
if(!used[i]){ //避免重复输出
cout<<caller[i];
used[i]=1; //更新状态
//依次输入与其同一电话圈的人物
for(int j=i+1;j<=n;j++){
if(circle[i][j]&&circle[j][i]&&!used[j]){
cout<<", "<<caller[j];
used[j]=1;
}
}
cout<<endl;
}
}
}
return 0;
}