http://www.lydsy.com/JudgeOnline/problem.php?id=3108

题意

原图中的一条边为新图中的一个点，原图中两条相接的边为新图中的一条边，即a→b为点ab，a→b→c为ab→bc。

题目要求根据新图判断是否存在一个原图。

题解

如果在新图中存在 i->k 和 j->k

那么在原图里一定是这样的

所以我们可以发现，如果存在i->k和j->k

但只存在i->t或j->t其中之一，则新图不合法。

O(N^3)验证

#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=301;
int n,m;bool a[N][N];

inline void init()
{
	memset(a,0,sizeof(a));
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=0;i<m;i++)
		scanf("%d%d",&x,&y),a[x][y]=1;
}

inline bool check()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			bool f1=0,f2=0;
			for(int k=0;k<n;k++)
			{
				if(a[i][k]&&a[j][k]) f1=true;
				if(a[i][k]!=a[j][k]) f2=true;
				if(f1&&f2) return 0;
			}
		}
	return 1;
}

int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		init();
		if(check()) puts("Yes");
		else puts("No");
	}
}