题129.算法竞赛入门 floyd 电话圈

• 题129.算法竞赛入门-floyd 电话圈
• 一、题目
• 二、题解

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

本题要求求出同一个电话圈的所有人，列出所有电话圈。根据题意我们知道，要在同一个电话圈，必须圈子里的人两两互通，形成闭环，则我们对原图用Floyd求出传递闭包，建立了一个新图，然后对新图dfs即可求出每一个电话圈，即连通分量。注意：深入dfs条件之一是两点互通。

#include 

using namespace std;

int N,M;
int G[25][25];
int visited[25];

void dfs(int v0)
{
    printf("%d ",v0);
    visited[v0]=1;
    for(int v=0;v>N>>M;
    fill(G[0],G[0]+25*25,0);
    for(int i=0;i>v1>>v2;
        G[v1][v2]=1;
    }
    //floyd求传递闭包，得到新的图
    for(int k=0;k