【ZOJ】1015 Fishing Net

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1015
제목: n 개의 점 이 없 는 방향 도 를 제시 하여 현 도 인지 물 어보 고 현 도 는 그림 의 임 의 길이 > 3 의 링 에 반드시 링 에 인접 하지 않 은 점 이 연결 되 어 있 음 (n < = 1000) 으로 정의 합 니 다.

#include <bits/stdc++.h>

using namespace std;



const int N=1005;

int n, m, ihead[N], cnt, tag[N], pos[N];

bool vis[N];

struct E { int next, to; }e[N*N];

void add(int u, int v) {

	e[++cnt]={ihead[u], v}; ihead[u]=cnt;

	e[++cnt]={ihead[v], u}; ihead[v]=cnt;

}

void cln() {

	memset(ihead, 0, sizeof(int)*(n+1));

	memset(tag, 0, sizeof(int)*(n+1));

	memset(pos, 0, sizeof(int)*(n+1));

	cnt=0;

}

bool check() {

	int x, y, mn, mx;

	for(int now=n; now; --now) {

		mx=-1; mn=~0u>>1; x=y=0;

		for(int i=1; i<=n; ++i) if(!pos[i] && tag[i]>mx) mx=tag[i], x=i;

		pos[x]=now;

		for(int i=ihead[x]; i; i=e[i].next) if(!pos[e[i].to]) tag[e[i].to]++;

		for(int i=ihead[x]; i; i=e[i].next) if(pos[e[i].to]>pos[x] && pos[e[i].to]<mn) mn=pos[e[i].to], y=e[i].to;

		for(int i=ihead[y]; i; i=e[i].next) vis[e[i].to]=1; vis[y]=1;

		for(int i=ihead[x]; i; i=e[i].next) if(pos[e[i].to]>pos[x] && !vis[e[i].to]) return 0;

		for(int i=ihead[y]; i; i=e[i].next) vis[e[i].to]=0; vis[y]=0;

	}

	return 1;

}

int main() {

	while(scanf("%d%d", &n, &m), n&&m) {

		int x, y;

		for(int i=0; i<m; ++i) { scanf("%d%d", &x, &y); add(x, y); }

		check()?puts("Perfect"):puts("Imperfect"); puts("");

		cln();

	}

	return 0;

}

　　
현도 판정 누 드 문제 =
현도 정의 위 에서 말 했다.
다음은 성질 을 말씀 드 리 겠 습 니 다.
단: 하나의 완전한 그림, 즉 단 중의 임의의 점 이 서로 연결 되 어 있다 는 것 이다.
단순 점: $x $와 그 인접 한 점 이 하나의 단 체 를 구성한다 면 $x $는 단순 점 입 니 다.
완벽 제거 시퀀스: 한 점 의 시퀀스, 각 점 에 한 번 씩 나타 나 고 임의의 $v 에 만족 합 니 다.i $, $v{i+1} \cdots v_{n} $의 유도 서브 맵 중 $vi $는 단순 한 점 입 니 다.
정리 1: 하나의 현 도 는 적어도 하나의 완벽 한 제거 서열 이 있다.(논문 을 증명 한다)
정리 2: 현도 의 유도 자 도 현도
그래서 누 드 로 완벽 한 서열 을 찾 는 알고리즘 은 완벽 한 서열 에 없 는 점 을 찾 을 때마다 현재 유지 보수 의 완벽 한 서열 에 가입 하여 단순 한 점 인지, 만약 에 가입 하 는 것 입 니 다.물론 누 드 폭력 입 니 다.
그래서 cdq 논문 은 두 가지 알고리즘 을 소개 했다.
우선 mcs 의 원 리 는 먼저 하나의 서열 을 찾 은 후에 이것 이 완벽 한 서열 을 없 애 는 것 인지 아 닌 지 를 판단 하 는 것 이다.그렇다면 mcs 알고리즘 은 어떻게 하나의 서열 을 찾 습 니까?
귀신 이 알 아!어쨌든 이것 은 욕심 QAQcdq 논문 인 것 같 습 니 다. QAQ 를 설명 하지 않 았 습 니 다. 매번 완벽 한 서열 앞 에 점 을 추가 합 니 다. 매번 가입 하 는 점 은 현재 유지 보수 서열 중의 점 과 가장 많이 연 결 된 서열 에 없 는 점 입 니 다. = 이것 은 무슨 귀신 입 니까?
그래서 알고리즘 은 매번 서열 중의 점 과 가장 많이 연 결 된 서열 에 없 는 점 을 찾 는 것 입 니 다. 가입 = =
마지막 으로 이 서열 이 합 법 적 인지 판단 합 니 다.
우리 가 $v 를 판단 하려 면i $이 점, 즉 $v{i+1} \cdots v_{n} $찾기 와 $vi $인접 한 점 집 $v{j_1}, v_{j_2}, \cdots v_{j k} $, 그리고 서열 에 따라 작은 것 부터 큰 것 까지 의 순서 입 니 다.그럼 우 리 는 $v 만 판단 해 야 합 니 다.{j 1} $와 $v{j i}, i > 1 $가 연결 되 어 있 는 지 여부 만 있 으 면 됩 니 다. 없 으 면 이 그림 은 현 그림 이 아 닙 니 다.이것 은 순서대로 서열 에 들 어 가 는 것 이기 때문에 우 리 는 또 이 점 집합 이 하나의 단체 라 고 요구 합 니 다. 그러면 우 리 는 서열 에서 가장 앞 에 있 는 $v 만 판단 해 야 합 니 다.{j 1} $가 다른 것 과 연결 되 어 있 는 지 여부 입 니 다. $v{j i}, i > 1 $가 판단 되 었 습 니 다 = =
가장 많은 점 을 찾 는 단계 에서 링크 로 $O (1) $까지 최적화 할 수 있 습 니 다. 하지만 저 는 너무 게 을 러 서 직접 폭력 = = 어차피 본 문 제 는 넘 을 수 있 습 니 다. $O (1) $를 사용 하지 않 아 도 set = = =