专栏首页用户6093955的专栏【Calling Circles UVA - 247 】【Floyd + dfs】

【Calling Circles UVA - 247 】【Floyd + dfs】

用到的东西

  1. Floyd算法(不考虑路径的长度,只关心两点之间是否有通路,可用于求有向图的传递闭包)
  2. STL map中的count用法
  3. 利用dfs输出同一个圈内的名字 题意 题目中给出 n 的人的名字,m组关系,表示前者给后者打电话 。如果两个人互相打过电话(直接或者间接),那么这两个人在一个集合。现在要求出所有集合中的人,输出格式看输出实例。 思路 设d[ i ] [ j ] 表示 i 和 j 通话过,如果 d[ i ] [ j ] && d[ j ] [ i ] 那么说明 i 和 j 属于同一个集合。 d[ i ][ j ] = d[ i ][ j ] ||(d[ i ][ k ] && d[ k ][ j ] ); AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<set>
#include<utility>
#include<map>
#include<string>
using namespace std;
const int maxn = 30;
int n, m;
string name1, name2;
int d[maxn][maxn], vis[maxn];
map<string, int> name_set;
vector<string> namee;
void dfs(int cur)
{
    vis[cur] = 1;
    for(int i = 0; i < n; i++)
    {
        if(!vis[i] && d[cur][i] && d[i][cur])
        {
            cout << ", " << namee[i];
            dfs(i);
        }
    }
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int cnt = 0;
    while(scanf("%d%d", &n, &m))
    {
        if(!n && !m) break;
        ++cnt;
        if(cnt != 1)
            cout << endl;
        name_set.clear();
        namee.clear();
        memset(d, 0, sizeof(d));
        int id = 0;
        for(int i = 0; i < m; i++)
        {
            cin >> name1 >> name2;
            if(!name_set.count(name1))
                name_set[name1] = id++, namee.push_back(name1);
            if(!name_set.count(name2))
                name_set[name2] = id++, namee.push_back(name2);
            d[name_set[name1]][name_set[name2]] = 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]);
        memset(vis, 0, sizeof(vis));
        cout << "Calling circles for data set " << cnt << ":" << endl;
        for(int i = 0; i < n; i++)
        {
            if(!vis[i])
            {
                cout << namee[i];
                dfs(i);
                cout << endl;
            }
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Frogger POJ - 2253(求两个石头之间”所有通路中最长边中“的最小边)

    ​ 题目主要说的是,有两只青蛙,在两个石头上,他们之间也有一些石头,一只青蛙要想到达另一只青蛙所在地方,必须跳在石头上。题目中给出了两只青蛙的初始位置,以及剩余...

    _DIY
  • 【Herding HDU - 4709 】【数学(利用叉乘计算三角形面积)】

    题意:给出n个点的坐标,问取出其中任意点围成的区域的最小值! 很明显,找到一个合适的三角形即可。

    _DIY
  • HDU-4544 湫湫系列故事——消灭兔子 (贪心+优先队列)

    将兔子的血量从大到小排列,将箭的属性写在类中(结构体也成),排序按照伤害从大到小排列,若有相等的则按价格从小到大排。

    _DIY
  • 和为0的最长连续子数组【转载+优化代码】

    题目描述和思路来自博客:http://www.cnblogs.com/coding-wtf/p/5849222.html,在此表示感谢。

    xiaoxi666
  • Kali Linux Web渗透测试手册(第二版) - 3.2 - 使用ZAP寻找敏感文件和目录

    thr0cyte,Gr33k,花花,MrTools,R1ght0us,7089bAt,

    用户1631416
  • 程序员探案之被吃掉的串口数据

    用户2196567
  • 算法:字符串的KMP模式匹配

    在朴素的模式匹配算法中,主串的pos值(i)是不断地回溯来完成的(见字符串的基本操作中的Index函数)。而计算机的大仙们发现这种回溯其实可以是不需要的。既然i...

    s1mba
  • 最小公倍数

    最小公倍数 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述 为什么1小时有60分钟,而不是100分钟呢?这是历史上的习惯导致...

    Gxjun
  • 关系型数据的分布式处理系统:Cobar

    Cobar简介 Cobar是关系型数据的分布式处理系统,它可以在分布式的环境下像传统数据库一样为您提供海量数据服务。 Github:https://github...

    Java技术栈
  • HDUOJ -----Color the ball

    Color the ball Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/327...

    Gxjun

扫码关注云+社区

领取腾讯云代金券