[UVA][graph] 11175 - From D to E and Back
Problem A
From D to E and back
Input: Standard Input
Output: Standard Output
|
Anyone who goes to a psychiatrist ought to have his head examined. |
Samuel Goldwyn
Take any directed graph D with n vertices and m edges. You can make the Lying graph E of D in the following way. E will have m vertices, one for each edge of D. For example, if D has an edge uv, then E will have a vertex called uv. Now, whenever D has edges uv and vw, E will have an edge from vertex uv to vertex vw. There are no other edges in E.
You will be given a graph E and will have to determine whether it is possible for E to be the Lying graph of some directed graph D.
Input
The first line of input gives the number of cases, N (N<220). N test cases
follow. Each one starts with two lines containing m
Output
For each test case, output one line containing "Case #x:" followed by either "Yes" or "No", depending on whether E is a valid Lying graph or not. Note that D is allowed to have duplicate edges and self-edges.
Sample Input Output for Sample Input
4210 150430 12 12 3390 10 21 21 02 02 10 01 12 2 |
Case #1: YesCase #2: YesCase #3: NoCase #4: Yes
|
Problem setter: Igor Naverniouk
Special Thanks: Joachim Wulff
全部檢查，對於 E 圖中的節點 v，所有指向 v 的節點，而這些節點必然指向同一個集合。
#include <stdio.h>
#include <algorithm>
using namespace std;
int g[305][305], gt[305];
int invg[305][305], invgt[305], to[305];
int check(int n) {
int i, j, k;
for(i = n-1; i >= 0; i--) {
for(j = 0; j < n; j++) to[j] = 0;
for(j = invgt[i]-1; j >= 0; j--) {
for(k = gt[invg[i][j]]-1; k >= 0; k--) {
to[g[invg[i][j]][k]]++;
}
}
for(j = 0; j < n; j++) {
if(to[j] == 0 || to[j] == invgt[i])
{}
else
return 0;
}
}
return 1;
}
int main() {
int t, cases = 0;
int n, m, i, x, y;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
for(i = 0; i < n; i++)
gt[i] = 0, invgt[i] = 0;
while(m--) {
scanf("%d %d", &x, &y);
g[x][gt[x]++] = y;
invg[y][invgt[y]++] = x;
}
int flag = check(n);
printf("Case #%d: %s\n", ++cases, flag ? "Yes" : "No");
}
return 0;
}