您现在的位置是:主页 > news > 自己怎么做彩票投注网站/如何加入广告联盟赚钱

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

admin2025/5/23 12:12:52news

简介自己怎么做彩票投注网站,如何加入广告联盟赚钱,网络技术公司,pc下载网传送门 题意:如果两个人相互打电话(直接或者间接),则说他们在同一个电话圈中,输入n个人的m次电话,找出所有的电话圈。 题解:首先用floyd求出传递凸包,当且仅当d[i][j]d[j][i]1时二者处于同一个电话圈&…

自己怎么做彩票投注网站,如何加入广告联盟赚钱,网络技术公司,pc下载网传送门 题意:如果两个人相互打电话(直接或者间接),则说他们在同一个电话圈中,输入n个人的m次电话,找出所有的电话圈。 题解:首先用floyd求出传递凸包,当且仅当d[i][j]d[j][i]1时二者处于同一个电话圈&…

传送门

题意:如果两个人相互打电话(直接或者间接),则说他们在同一个电话圈中,输入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;
}