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

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

题目描述

采用任意有n个顶点和m个边的有向图D. 您可以通过以下方式制作D的Lying图E. E将有m个顶点，每个用于表示D的每个边。例如，如果D具有边(u,v)，则E将具有称为uv的顶点。现在，每当D具有边(u,v)和(v,w)时，E将具有从顶点uv到顶点vw的边。 E中没有其他边。您将获得一个图E，并且必须确定E是否可能是某个有向图D的Lying图。

输入

输入的第一行给出案例数N (N < 220)。接下来是N个测试用例。每一个开始两行分别包含m(0≤m≤300)和k。接下来的k行每一行包含一对顶点，即e中存在一条从x到y的边。顶点编号从0到m−1.

输出

对于每个测试用例，输出一行包含’ case #x: ‘，后面跟着’ Yes ‘或’ No '，具体取决于具体情况,E是否是一个有效的Lying图。注意，D允许有重复的边和自边。

输入样例

4
2
1
0 1
5
0
4
3
0 1
2 1
2 3
3
9
0 1
0 2
1 2
1 0
2 0
2 1
0 0
1 1
2 2

输出样例

Case #1: Yes
Case #2: Yes
Case #3: No
Case #4: Yes

题目分析

这个题主要考察图的临界矩阵的使用
①实际上就是把有向图D中得边缩点，有向图D中得一条边对应图E中得一个点，如果存在D具有边(u,v)和(,w)时，E将具有从顶点uv到顶点vw的边。
如图所示:

②如果i边和j边有公共端点，则i连接的边j一定也连接。不存在i连接的边j没连接的情况。下图中E图i,j存在公共点,这时候E图中i能连接的点,j也能连接.所以最后一个E图不成立,是错的.

代码演示

#include<iostream>
#include<string.h>
using namespace std;
#define REP(i,b,e) for(int i = b; i < e; i++)
const int maxn = 305;
int g[maxn][maxn], n, m, cnt;
bool solve()
{
   
	REP(i, 0, n)
	{
   
		REP(j, 0, n)
		{
   
			bool flag1 = false, flag2 = false;
			REP(k, 0, n)
			{
   
				if (g[i][k] && g[j][k])// 存在公共节点
				{
   
					flag1 = true;
				}
				if (g[i][k] ^ g[j][k])//存在i->k和j->k只成立一个.
				{
   
					flag2 = true;
				}
				if (flag1 && flag2)
					return false;
			}
			
		}
	}
	return true;	
}

int main()
{
   
	int T,x,y;//cnt:用于计数
	cin >> T;
	while (T--)
	{
   
		cin >> n >> m;
		memset(g, 0, sizeof(g));//初始化邻接矩阵g
		REP(i, 0, m)
		{
   
			cin >> x >> y;
			g[x][y] = 1;
		}
		if (solve())
		{
   
			cout << "Case #" << ++cnt << ": " << "Yes" << endl;
		}
		else
		{
   
			cout << "Case #" << ++cnt << ": " << "No" << endl;
		}

	}
	return 0;
}

代码分析

1. 首先这个题中判断两顶点边的次数较多,所以应使用邻接矩阵.
2. 判断(i , k), (j , k) 边是否存在时,涉及到了三个变量,所以应该使用三层循环,一个变,另外两个不变.
3. 此题精妙之处在于判断是否存在k,当i,j有公共顶点时,如果 (i , k ),(j , k)
   中,只有一个成立,说明该E图不能由D图化来.原因在于:前面说过了.为此可以用 ^ 来实现,当两个条件只有一个成立时,便为真.

心得收获

1. 如果题中循环过多,也可以采用宏定义的方式.
2. ^ 的使用:当两个条件只有一个成立结果为真.