题意:

如果两个人相互打电话,则说他们在同一个电话圈里。例如,a打给b,b打给c,c打给d,d打给a,则这4个人在同一个圈里;如果e打给f但f不打给e,则不能推出e和f在同一个电话圈里,输出所有电话圈。

//floyd求传递闭包,dfs求出电话圈;

//还有循环一定从0开始啊,标记人也要 第0个,第1个,第2个。。。。。因为动态数组你一压进去就是从0开始

//所以你之前做才一直错啊  从0开始

 #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
string s1,s2;//姓名
int n,m;
vector<string>name;//动态数组名字
map<string,int>ID;//把人给编号
int vis[];//是否访问
int d[][];//是否能通电话
void dfs(int k)//深搜求电话圈
{
vis[k]=;
for(int i=;i<n;i++)
{
if(!vis[i]&&d[i][k]&&d[k][i])
{
cout<<name[i]<<" ";
dfs(i);
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)//n个人m个电话圈
{
memset(vis,,sizeof(vis));
memset(d,,sizeof(d));
int cnt=;
name.clear();
ID.clear();
for(int i=;i<=m;i++)
{
cin>>s1>>s2;
if(!ID.count(s1))//这个人没有
{
ID[s1]=cnt++;//给这个人编号
name.push_back(s1);//进入队列
}
if(!ID.count(s2))
{
ID[s2]=cnt++;
name.push_back(s2);
}
int x=ID[s1];
int y=ID[s2];
d[x][y]=;//这两个人可以互相通电话
}
for(int k=;k<n;k++)//floyd
for(int i=;i<n;i++)
for(int j=;j<n;j++)
d[i][j]=d[i][j]||d[i][k]&&d[k][j];
for(int i=;i<n;i++)//求电话圈
{
if(!vis[i])
{
cout<<name[i]<<" ";
dfs(i);
printf("\n");//在这里有个回车。。不然没形成一个电话圈时,它会输出一个电话圈
}
}
}
}

//学到的floyd判圈,dfs求圈

05-21 10:14