解題區/解題區 - UVa

UVa 11893 - Fabulous DAGy

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

原本是一張 DAG，增加一條有向邊會使得存有一個環，而這個環將會通過所有的點一次。

現在給予加完後的結果，是否存在一條有向邊，使得原本的 DAG 變成符合上述條件的圖。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
3 3
0 1
1 2
2 0
4 5
0 1
1 2
2 0
0 3
3 2

Sample Output

1
2
Yeah, I'm superman
Your DAGy was initially defected!

Solution

由於只能通過所有點一次的環，對於 DAG 而言，替除掉應該加入的邊會發現到拓樸排序只能是唯一的長鏈狀。

因此窮舉拔掉所有可能的邊，並且檢查是否能夠符合長鏈狀的拓樸順序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int indeg[512], outdeg[512], mg[512][512];
vector<int> g[512];
int check(int st, int banu, int banv, int n) {
    queue<int> Q;
    int in[512], out[512], visited = 0, u, v;
    for(int i = 0; i < n; i++)
        in[i] = indeg[i], out[i] = outdeg[i];
    Q.push(st), in[banv]--, out[banu]--;
    while(!Q.empty()) {
        u = Q.front(), Q.pop();
        visited++;
        for(int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if(--in[v] == 0)
                Q.push(v);
        }
        if(Q.size() > 1)	return 0;
    }
    return visited == n && mg[u][st];
}
int main() {
    int testcase, n, m, u, v;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        memset(mg, 0, sizeof(mg));
        memset(indeg, 0, sizeof(indeg));
        memset(outdeg, 0, sizeof(outdeg));
        for(int i = 0; i < n; i++)
            g[i].clear();
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            mg[u][v] = 1;
            g[u].push_back(v);
            indeg[v]++, outdeg[u]++;
        }
        int ret = 0;
        for(int i = 0; i < n && !ret; i++) {
            for(int j = 0; j < g[i].size() && !ret; j++) {
                u = i, v = g[i][j];
                if(indeg[v] == 1 && outdeg[u] == 1) {
                    ret |= check(v, u, v, n);
                }
            }
        }
//		puts(ret ? "YES" : "NO");
        puts(ret ? "Yeah, I'm superman" : "Your DAGy was initially defected!");
    }
    return 0;
}
/*
5 6
0 1
1 2
2 3
3 4
4 0
1 3
*/