题目来源：

https://vjudge.net/contest/292206#problem/E

http://acm.fzu.edu.cn/problem.php?pid=1924 

Problem Description

在操作系统中存在着死锁问题。

进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了死锁。

例如，如果线程A占用了资源1并等待资源2，而线程B占用了资源2并等待资源1，这样两个线程就发生了死锁现象。

为了描述系统资源分配的问题，我们用一张有向图G来表示资源分配图。V为有向图的顶点集，包括进程结点集合P={p1,p2,…,pn}和资源结点集合R={r1,r2,…,rm}两种；E为有向边的集合，其元素包括二元组(pi,rj)或(rj,pi)。(pi,rj)表示进程pi申请资源rj，(rj,pi)表示资源rj被进程pi占用。

根据操作系统中的知识可以知道，如果在一个资源分配图中，从任意一个结点出发，都不存在一条路径能回到自身，则系统中没有死锁，否则系统中可能存在死锁。

你的任务是对于给你的一张资源分配图，判断是否可能存在死锁。

Input

输入第一行是一个整数T,，表示有T组数据。

每组数据的第一行是四个整数P,R,E1,E2,其中P表示进程结点数，R表示资源结点数，E1表示(pi,rj)边数，E2表示(rj,pi)边数，1 <= P,R <= 500。接下来E1行每行两个整数pi,rj,表示从结点pi到rj有一条边。接下来E2行每行两个整数rj,pi，表示从结点rj到pi有一条边。0 <= pi < P, 0 <= rj <R。

Output

对于每组数据输出一行先输出组数(从1开始)，接着如果可能存在死锁输出”Possible”；如果不可能存在死锁输出一行“Impossible”。

 Sample Input

2 2 2 1 1 0 1 0 1 3 3 3 4 0 0 1 1 2 2 0 1 2 0 2 1 1 2

Sample Output

Case 1: Impossible Case 2: Possible

Source

FOJ有奖月赛-2010年06月

题意：给定两个占用关系集合，判断有没有死锁，也就是有没有环的存在。

思路：定义两个关系数组，pre和rep分别存其占用关系，初始化为-1表示没有被占用，从1到p1遍历进程结点，用两关系数组找到父节点，book数组标记当前结点是否存在于死锁中（我们把死锁所在的环看做一颗树）（啊啊啊，这就是并查集吧，比赛的时候一直在整最短路，原来是题目没读懂）。

思想是并查集，但是打并查集板子并不会做。。。学长说的拓扑排序也得学一学了。

参考代码：

//#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=500+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
int pre[N],rep[N];
bool book[N];
struct node {};
int main()
{
#ifdef DEBUG
    freopen("input.in", "rep", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    for(int k=1; k<=t; k++)
    {
        memset(book,0,sizeof(book));
        memset(pre,-1,sizeof(pre));
        memset(rep,-1,sizeof(rep));
        int p1,r1,e1,e2;
        scanf("%d%d%d%d",&p1,&r1,&e1,&e2);
        for(int i=0; i<e1; i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            pre[a]=b;
        }
        for(int i=0; i<e2; i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            rep[a]=b;
        }
        bool flag=0;
        for(int i=0; i<p1; i++)
        {
            memset(book,0,sizeof(book));
            book[i]=1;
            if(pre[i]==-1)
                continue;
            int t=rep[pre[i]];
            if(t==-1)
                continue;
            while(book[t]!=1)
            {
                if(t==-1)
                    break;
                if(pre[t]==-1)
                    break;
                book[t]=1;
                t=rep[pre[t]];
            }
            if(t!=-1&&book[t]==1&&pre[t]!=-1)
            {
                flag=1;
                break;
            }
        }
        if(flag)
            printf("Case %d: Possible\n",k);
        else
            printf("Case %d: Impossible\n",k);
    }

#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}