自己怎么做彩票投注网站/如何加入广告联盟赚钱

传送门

题意：如果两个人相互打电话(直接或者间接)，则说他们在同一个电话圈中，输入n个人的m次电话，找出所有的电话圈。

题解：首先用floyd求出传递凸包，当且仅当d[i][j]=d[j][i]=1时二者处于同一个电话圈，构造一个新图，在一个电话圈里的两个人之间连一条边，然后依次输出各个连通分量的所有人即可。

附上代码：

#include<bits/stdc++.h>using namespace std;const int maxn=30;
const int maxm=1e3+50;int n,m;
int d[maxn][maxn];vector<string>name;int trans(string temp)
{int ssize=name.size();for(int i=0;i<ssize;i++){if(temp==name[i]){return i;}}name.push_back(temp);return ssize;
}bool done[maxn];void dfs(int u)
{done[u]=1;for(int v=0;v<n;v++){if(!done[v]&&d[u][v]&&d[v][u]){cout<<", "<<name[v];dfs(v);}}
}int main()
{int casen=1;while(cin>>n>>m){if(n==0&&m==0){break;}else{for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j){d[i][j]=1;}else{d[i][j]=0;}}}name.clear();string temp1,temp2;for(int i=0;i<m;i++){cin>>temp1>>temp2;d[trans(temp1)][trans(temp2)]=1;}for(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){d[i][j]=d[i][j]||(d[i][k]&&d[k][j]);}}}if(casen>1){printf("\n");}memset(done,false,sizeof(done));cout<<"Calling circles for data set "<<casen++<<":"<<endl;for(int i=0;i<n;i++){if(!done[i]){cout<<name[i];dfs(i);cout<<endl;}}}}return 0;
}