电话圈

紫书P365

【题目类型】Floyd传递闭包+输出连通分量

&题解：

原来floyd还可以这么用，再配合连通分量，简直牛逼。

我发现其实求联通分量也不难，就是for循环+dfs+vis记录数组。

在发上刘汝佳的代码链接：https://github.com/aoapc-book/aoapc-bac2nd/blob/master/ch11/UVa247.cpp

【时间复杂度】O(\(n^3\))

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d %d",&(N),&(M))

#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))

#define rep(i,b) for(int i=0;i<(b);i++)

#define rez(i,a,b) for(int i=(a);i<=(b);i++)

#define red(i,a,b) for(int i=(a);i>=(b);i--)

const ll LINF = 0x3f3f3f3f3f3f3f3f;

#define PU(x) puts(#x);

#define PI(A) cout<<(A)<<endl;

#define DG(x) cout<<#x<<"="<<(x)<<endl;

#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;

#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS = 1e-9 ;

/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */

const int MAXN = 50 + 5 ;

int n,m,d[MAXN][MAXN],ka;

bool v[MAXN];

vector<string> names;

int ID(string s){

	for (int i=0;i<names.size();i++){

		if (s==names[i]) return i;

	}

	names.push_back(s);

	return names.size()-1;

}

void dfs(int x){

	v[x]=1;

	for(int i=0;i<n;i++){

		if (!v[i]&&d[x][i]&&d[i][x]){

			printf(", %s",names[i].c_str());

			dfs(i);

		}

	}

}

void Solve()

{

    while(~SII(n,m),n||m){

    	names.clear();

    	cle(d,0);

    	char s1[MAXN],s2[MAXN];

    	rep(i,m) {

    		scanf("%s%s",s1,s2);

    		d[ID(s1)][ID(s2)]=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][k]&&d[k][j];

    	if(ka) PU();

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

    	cle(v,0);

    	for (int i=0;i<n;i++){

    		if (!v[i]){

    			printf("%s",names[i].c_str());

    			dfs(i);

    			printf("\n");

    		}

    	}

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("1.in", "r", stdin);

    freopen("1.out","w",stdout);

#endif

//iostream::sync_with_stdio(false);

//cin.tie(0), cout.tie(0);

    // int T;cin>>T;while(T--)

    Solve();

    return 0;

}

秒客网

UVA 247 电话圈(Floyd传递闭包+输出连通分量)

电话圈

相关文章