[UVA][搜索] 840 - Deadlock Detection
Deadlock Detection
| Deadlock Detection |
In Operating Systems a special resource-allocation graph algorithm can be used to detect whether there is any deadlock in the system. A resource-allocation graph is a directed graph consisting of two different types of nodes P = P1, P2,..., Pn, the set consisting of all active processes in the system, and R = R1, R2,..., Rm, the set consisting of all resource types in the system.
A directed edge from process Pi to resource
Rj is denoted by
Pi 
Rj
and means that process Pi requested an
instance resource type Rj, and is currently waiting for that
resource. A directed edge from resource type Rj
to process Pi, is
denoted by
Rj Pi and means that an instance of
resource type Rj has been allocated to process Pi.
The following figure illustrates a resource-allocation graph where processes are denoted by circles and resources by squares. Notice that if there is a circular wait among the processes, then it implies that a deadlock has occurred.
Given a resource allocation graph in which each resource type has exactly one instance, your job is to determine whether there is a deadlock in the system. In case a deadlock exists, you must also show the sequence of processes and resources involved.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
We will assume that processes are named by capital letters and resources by small letters, so we limit to 26 the number of processes and/or resources. Therefore, the first line of input consists of three numbers N, M and E, respectively, the number of processes, the number of resources and the number of edges. The edges are given in the following lines as pairs of letters linked by a `-' character. Edges are separated by spaces or newlines.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
The output must be `NO' if no deadlock is detected. In case a deadlock is detected, the output must be `YES' followed by the sequence or sequences of circular waits detected, one per line. If more then one sequence is found, they should all be output in increasing order of their length.
Sample Input
1 2 2 4 A-b B-a a-A b-B
Sample Output
YES A-b-B-a-A
Fernando Silva, ACM-UP'2001
吶，題目看不是很懂。
Input :
3
2 2 4
Y-a a-X X-b b-Y
2 2 4
Y-a a-Y X-b b-X
2 2 5
Y-a a-X X-b b-X b-Y
Output:
YES
X-b-Y-a-X
YES
X-b-X
Y-a-Y
YES
X-b-X
X-b-Y-a-X
同一種環，只保留字典順序最小的。
且長度越小越早輸出，字典順序越小越早輸出。
總之，就這麼 AC 了。
#include <stdio.h>
#include <vector>
#include <iostream>
#include <set>
using namespace std;
vector<int> g[60];
int used[60], path[120];
set<string> ansbuf[150];
void save(int dep) {
int i, j, buf[60], flag;
for(i = 0; i <= dep; i++)
buf[i] = path[i];
for(i = dep+1, j = 1; j <= dep; j++, i++)
path[i] = path[j];
for(i = 1; i <= dep; i++) {
flag = 0;
for(j = 0; j <= dep; j++) {
if(path[i+j] < buf[j]) {
flag = 1;
break;
}
if(path[i+j] > buf[j]) {
flag = -1;
break;
}
}
if(flag == 1) {
for(j = 0; j <= dep; j++)
buf[j] = path[i+j];
}
}
string ans = "";
for(j = 0; j <= dep; j++) {
if(j) ans += "-";
if(buf[j] >= 26)
ans = ans + (char)(buf[j]-26+'a');
else
ans = ans + (char)(buf[j]+'A');
}
ansbuf[ans.length()].insert(ans);
}
void dfs(int idx, int st, int dep) {
used[idx] = 1;
int i;
for(i = 0; i < g[idx].size(); i++) {
if(g[idx][i] == st) {
path[dep+1] = g[idx][i];
save(dep+1);
}
if(used[g[idx][i]] == 0) {
path[dep+1] = g[idx][i];
dfs(g[idx][i], st, dep+1);
}
}
used[idx] = 0;
}
int main() {
int t, n, m, e;
int i, j, k;
char s[100], x, y;
scanf("%d", &t);
while(t--) {
scanf("%d %d %d", &n, &m, &e);
for(i = 0; i < 52; i++)
g[i].clear();
while(e--) {
scanf("%s", s);
sscanf(s, "%c-%c", &x, &y);
if(x >= 'a') x = x-'a'+26;
else x = x-'A';
if(y >= 'a') y = y-'a'+26;
else y = y-'A';
g[x].push_back(y);
}
for(i = 0; i < 52; i++) {
path[0] = i;
dfs(i, i, 0);
}
int flag = 0;
for(i = 0; i < 150; i++)
if(ansbuf[i].size())
flag = 1;
if(flag == 0) {
puts("NO");
} else {
puts("YES");
for(i = 0; i < 150; i++) {
for(set<string>::iterator it = ansbuf[i].begin();
it != ansbuf[i].end(); it++)
cout << *it << endl;
ansbuf[i].clear();
}
}
if(t)
puts("");
}
return 0;
}