bzoj 1242: Zju1015 Fishing Net 弦图判定

1242: Zju1015 Fishing Net弦图判定

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 214 Solved: 81
[Submit][Status][Discuss]

Description

在一个高度信息化的渔村，鱼网的制作和修补都是由电脑完成。众所周知，鱼网是由网组成的(废话)，网组成的东西叫网眼。如果网眼够小，就能捕到很多鱼；如果网眼太大，鱼就会全部漏走。每次捕鱼回来，鱼网都会烂得很厉害，小网眼会变成网眼，那鱼网就需要修补。他们希望有一个程序能够为他们判断鱼网是否需要修补。程序会把鱼网看作一个联通的图(不用进一步解释了吧)。他们的判断方法是：任何一个长度(组成其的边的数目)超过3的闭合的圈，都必须有一条交线将它分作两部分。(提示：递归下去，其实就是每个网眼都只能是三角形)如果合乎要求，程序就输出“Perfect",否则输出"Imperfect". 注：这里的交线是指一个联结一封闭圈的不同结点而捕属于该圈的一条边。

Input

数据以一行N M开始，表示鱼网有N个结点和M条边。(n<=0<=1000)以下M行是M条边的描述。每行两个整数A，B，表示结点A与结点B之间存在一条边。

Output

输出每个鱼网的测试结果，Perfect或Imperfect

Sample Input

4 4
1 2
2 3
3 4
4 1

Sample Output

Imperfect

HINT

Source

弦图判定

　　弦图裸题，就是边的范围是n^2，而不是n。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
#define MAXN 1010
#define MAXE MAXN*MAXN*2
#define MAXV MAXN
struct Edge
{
        int np;
        Edge *next;
}E[MAXE],*V[MAXV];
int tope=-1;
void addedge(int x,int y)
{
        E[++tope].np=y;
        E[tope].next=V[x];
        V[x]=&E[tope];
}
bool vis[MAXN];
int deg[MAXN];
priority_queue<pair<int,int> > PQ;
vector<int> seq;
int rk[MAXN];
set<pair<int,int> > S;

int main()
{
        freopen("input.txt","r",stdin);
        int n,m;
        scanf("%d%d",&n,&m);
        int x,y;
        for (int i=0;i<m;i++)
        {
                scanf("%d%d",&x,&y);
                if (S.find(make_pair(x,y))!=S.end())continue;
                addedge(x,y);
                addedge(y,x);
                S.insert(make_pair(x,y));
                S.insert(make_pair(y,x));
        }
        PQ.push(make_pair(0,1));
        while (!PQ.empty())
        {
                Edge *ne;
                pair<int,int> pr=PQ.top();
                PQ.pop();
                if (vis[pr.second] || deg[pr.second]!=pr.first)continue;
                seq.push_back(pr.second);
                vis[pr.second]=true;
                for (ne=V[pr.second];ne;ne=ne->next)
                {
                        if (!vis[ne->np])
                        {
                                deg[ne->np]++;
                                PQ.push(make_pair(deg[ne->np],ne->np));
                        }
                }
        }
        if (seq.size()!=n)
        {
//                printf("Imperfect
");
//                return 0;
        }
        for (int i=0;i<seq.size()/2;i++)
                swap(seq[i],seq[seq.size()-1-i]);
        for (int i=0;i<seq.size();i++)
                rk[seq[i]]=i;
        vector<int> vec;
        for (int i=0;i<seq.size();i++)
        {
                int now=seq[i];
                Edge *ne;
                vec.clear();
                for (ne=V[now];ne;ne=ne->next)
                {
                        if (rk[ne->np]>rk[now])
                        {
                                vec.push_back(rk[ne->np]);
                        }
                }
                sort(vec.begin(),vec.end());
                for (int i=0;i<vec.size();i++)
                        vec[i]=seq[vec[i]];
                for (int i=1;i<vec.size();i++)
                {
                        if (S.find(make_pair(vec[0],vec[i]))==S.end())
                        {
                                printf("Imperfect
");
                                return 0;
                        }
                }
        }
        printf("Perfect
");
}