FZU Problem 1924 死锁

Problem 1924 死锁

Accept: 93 Submit: 244
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

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

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

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

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

为了描述系统资源分配的问题，我们用一张有向图G来表示资源分配图。V为有向图的顶点集，包括进程结点集合P={p₁,p₂,…,p_n}和资源结点集合R={r₁,r₂,…,r_m}两种；E为有向边的集合，其元素包括二元组(p_i,r_j)或(r_j,p_i)。(p_i,r_j)表示进程p_i申请资源r_j，(r_j,p_i)表示资源r_j被进程p_i占用。

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

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

Input

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

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

Output

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

Sample Input

2 2 1 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

//并查集判断是否有环
//把R集合的编号统统加上P，就可以了

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <cmath>
#define N 1004
using namespace std;
int f[N],r[N];
int Find(int x)
{
    if(x!=f[x])
    {
        return f[x]=Find(f[x]);
    }
    return x;
}
bool flag;
int main()
{
  int P,R,E1,E2,n;
  int p,r;
  int i,T,t=1;
  scanf("%d",&T);
  while(T--)
  {scanf("%d%d%d%d",&P,&R,&E1,&E2);
      n=P+R;
      for(i=0;i<n;i++)
       f[i]=i;
       flag=1;
      while(E1--)
      {
          scanf("%d%d",&p,&r);
          p=Find(p);
          r=Find(r+P);
          if(p==r) flag=0;
          f[r]=p;
      }
      while(E2--)
      {
          scanf("%d%d",&r,&p);
          r=Find(r+P);
          p=Find(p);
          if(r==p) flag=0;
          f[p]=r;
      }
      printf("Case %d: ",t++);
      if(!flag) printf("Possible\n");
      else printf("Impossible\n");
  }
}