洛谷 题解 UVA247 【电话圈 Calling Circles】

【题意】

如果两个人互相打电话（直接或者间接），则说他们在同一个电话圈里。例如，\(a\)打给\(b\)，\(b\)打给\(c\)，\(c\)打给\(d\)，\(d\)打给\(a\)，则这四个人在同一个圈里；如果\(e\)打给\(f\)，而\(f\)不打给\(e\)，则不能推出\(e\)和\(f\)在同一个电话圈。输入\(n(n≤25)\)个人的\(m\)次电话，找出所有的电话圈。人名只包含字母，不超过\(25\)个字符，且不重复。

【算法】

\(Floyd\text{传递闭包}\)

【分析】

首先用\(Floyd\)求出传递闭包，即g[i][j]表示i是否直接或间接向j打过电话，当且仅当g[i][j]=g[j][i]=1时二者处于同一个电话圈。构造一个新图，在“一个电话圈里”的两个人之间连一条边，然后依次输出各个联通分量的所有人即可。

【代码】

#include<bits/stdc++.h>

using namespace std;

map<string,int>mp;

string st[30];

string st1,st2;

bool g[30][30];

bool used[30];

int sum;

int n,m;

int T;

int main()

{

	cin>>n>>m;

	while(1)

	{

		sum=0;

		T++;

		//cout<<T<<endl;

		memset(g,0,sizeof(g));

		memset(used,0,sizeof(used));

		mp.clear();

		for(int i=1;i<=m;i++)

		{

			cin>>st1>>st2;

			if(!mp[st1])

			{

				mp[st1]=++sum;

				st[sum]=st1;

			}

			if(!mp[st2])

			{

				mp[st2]=++sum;

				st[sum]=st2;

			}

			g[mp[st1]][mp[st2]]=1;

		}

		for(int k=1;k<=n;k++)

		{

			for(int i=1;i<=n;i++)

			{

				for(int j=1;j<=n;j++)

				{

					g[i][j]=g[i][j] || (g[i][k] && g[k][j]);

				}

			}

		}

		printf("Calling circles for data set %d:\n",T);

		/*for(int i=1;i<=n;i++)

			cout<<st[i]<<" ";cout<<endl;*/

		for(int i=1;i<=n;i++)

		{

			if(!used[i])

			{

				cout<<st[i];

				used[i]=1;

				for(int j=1;j<=n;j++)

				{

					if(g[i][j]&&g[j][i]&&!used[j])

					{

						cout<<", "<<st[j];

						used[j]=1;

					}

				}

				cout<<endl;

			}

		}

		cin>>n>>m;

		if(n||m)cout<<endl;

		else break;

	}

	return 0;

}

刘汝佳大法好！