图论--传递闭包（Floyd模板）

代码语言：javascript复制

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int dp[105][105],in[105],out[105];
int init()
{
	for(int i=1;i<=105;i  )
	{
		in[i]=0;
		out[i]=0;
		for(int j=1;j<=100;j  )
		{
			dp[i][j]=0;
		}
	}
}
int main()
{
	long long  t;
	cin>>t;
	while(t--)
	{
		init();
		long long n,m;
		cin>>n>>m;
        long long flag=0;
		for(int i=1;i<=m;i  )
		{
			long long  l,r;
			cin>>l>>r;
			dp[l][r]=1;
			if(l==r)    flag=1; //自己排在自己前面是不可能的，直接按题意输出0
		}
		for(int k=1;k<=n;k  )
			for(int i=1;i<=n;i  )
				for(int j=1;j<=n;j  )
					dp[i][j]=(dp[i][k]&&dp[k][j]);//floyd 讨论图的连通性

		for(int i=1;i<=n;i  )
			for(int j=1;j<=n;j  )
				if(dp[i][j]==1&&dp[j][i]==1)
					flag=1;
        //floyd 讨论图的连通性后，如果出现环的话，就是我排在你前面。你排在我前面，同样不可能
		for(int i=1;i<=n;i  )
			for(int j=1;j<=n;j  )
				if(dp[i][j]==1)
				{
					in[i]  ;    //有几个人排在第I个人前面
					out[j]  ;//有几个人排在第j个人后面面
				}
		if(flag)  //不符合现实的按题意输出0
		{
			for(int i=1;i<=n;i  )cout<<"0";
			cout<<endl;
		}
		else
		{
			for(int i=1;i<=n;i  )
			{
				if(in[i]>=(n 1)/2||out[i]>=(n 1)/2)  cout<<"0";
				//如果在他前面或者在他后面的不等于一般的人数，他绝对不是中间位置
				else   cout<<"1";
			}
			cout<<endl;
		}
	}
	return 0;
 }

闭包

0 人点赞