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 = P₁, P₂,..., P_n, the set consisting of all active processes in the system, and R = R₁, R₂,..., R_m, the set consisting of all resource types in the system.

A directed edge from process P_i to resource R_j is denoted by P_i R_j and means that process P_i requested an instance resource type R_j, and is currently waiting for that resource. A directed edge from resource type R_j to process P_i, is denoted by R_j P_i and means that an instance of resource type R_j has been allocated to process P_i.

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;
}