21.09.13模拟 保存名画

对于一个任务，有n个步骤，其中一些步骤要前置步骤完成后才能做，每个步骤要求在1号或者2号实验室做，要求在两个实验室之间往返的次数最少

初始点题目没说，就是1或2都可以，我们要分类讨论，然后拓扑即可，往返移动

#include<iostream>
#include<cstdio>
#include<queue>
//#include<windows.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
#define bug cout<<"~~~~~~~~~~~~~"<<'
';
#define bugout(x) cout<<x<<endl;
typedef long long lxl;
template<typename T>
inline T  max(T &a, T &b) {
	return a > b ? a : b;
}
template<typename T>
inline T  min(T a, T b) {
	return a < b ? a : b;
}

inline char gt() {
	static char buf[1 << 21], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void  read(T &x) {
	register char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x, char cc) {
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar(cc);
}
const int N = 3e5 + 79;
const int M = 2e6 + 79;
int degree[N], n, m, a[N], tot, in[N];
struct graph {
	int head[N], tot, next[M], ver[M];
	inline void add(int a, int b) {
		ver[++tot] = b;
		next[tot] = head[a];
		head[a] = tot;
	}
} G;
int q[N];
int temp[N], cnt;
inline int topsort(int st) {
	int step(0);
	rep(i, 1, n) in[i] = degree[i];
	q[q[0] = 1] = 0; 
	a[0] = st;
	int pos(st);
	while(1) {
		step++;
		rep(i, 1, cnt) {
			q[++q[0]] = temp[i];
		}
		cnt = 0;
		rep(kkk, 1, q[0]) {

			int x = q[kkk];
			for(register int i(G.head[x]); i; i = G.next[i]) {
				int y(G.ver[i]);
				in[y]--;
				if(!in[y] && a[y] == pos) q[++q[0]] = y;
				else if(!in[y]) temp[++cnt] = y;
			}
		}
		q[0] = 0;
        
		pos++;
		if(pos == 3) pos = 1;
		if(!cnt) break;
	}
	return step - 1;
}



int main() {
	freopen("save.in", "r", stdin);
	freopen("save.out", "w", stdout);
	read(n);
	read(m);

	rep(i, 1, n) {
		read(a[i]);
		G.add(0, i);
		degree[i]++;
	}
	int x, y;
	rep(i, 1, m) {
		read(x);
		read(y);
		G.add(x, y);
		degree[y]++;
	}
	out(min(topsort(1), topsort(2)), '
');
	return 0;
}