UVA11175有向图D和E From D to E and Back题解

题目

链接

https://www.luogu.com.cn/problem/UVA11175

字面描述

D 为有向图， D 的每条边对应 E 的一个结点，若 D有边 uv，则 E 有结点 uv，对于 D 的两条边 uv 和 vw， E 中的两个结点 uv 与 vw 连边。给出 E，判断是否有对应的 D。

思路

本人一开始读了很久题都没读懂，参考了一下题解，简单讲讲思路

1. 枚举3个点
2. 如果前两个点都有到第三个点的边，记录1
3. 如果只有一个有，记录2
4. 在第三层循环结束判断记录1和记录2是否同时存在
   同时存在，错误
   否则，继续
   这是因为，两个点可以同时到多个点，但突然出现一个只有一个点能到达的点，这是图就还原不回去了，所以要判断。
5. 最后没出现错误，正确

代码实现

#include<bits/stdc++.h>
using namespace std;

const int maxn=300+10;
int n,m,k;
bool vis[maxn][maxn];
inline bool solve(){
    
	for(int i=0;i<m;i++){
    
		for(int j=0;j<m;j++){
    
			bool flag1=false,flag2=false;
			for(int k=0;k<m;k++){
    
				if(vis[i][k]&&vis[j][k])flag1=true;
				if(vis[i][k]^vis[j][k])flag2=true;
			}
			if(flag1&&flag2)return false;
		}
	}
	return true;
}
int main(){
    
	scanf("%d",&n);
	int N=n;
	while(n--){
    
		printf("Case #%d: ",N-n);
		memset(vis,false,sizeof(vis)); 
		scanf("%d%d",&m,&k);
		for(int i=1;i<=k;i++){
    
			int x,y;
			scanf("%d%d",&x,&y);
			vis[x][y]=true;
		}
		if(solve())printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}