P9697 Canvas 题解

首先观察到有一个关键性质是 \(1 \leq x_i,y_i \leq 2\)。

那么我们贪心的考虑我们肯定会将 \((x,y)=(1,1)\) 的在一开始操作，\((x,y)=(2,2)\) 的最后操作。

也就是说现在没有固定的是 \((x,y)=(1,2)\) 和 \((x,y)=(2,1)\) 的。

我们不妨令 \((x,y)=(1,2)\)，然后连边 \((l,r)\)。

然后我们需要依次选择每一条边 \((u,v)\)，这个操作相当于赋值 \(a_v =2\) 和赋值 \(a_u=1\)。

然后我们可以容易构造出来一个强联通分量中经过一系列操作至多有一个 \(a=1\) 的节点，并且一定有一个 \(a=1\) 的节点，具体的随便搜出一个这个分量中的 dfs 树然后从叶子开始操作即可。

那么缩强联通分量使图变成 DAG 之后如果一个点没有前驱那么意味着这一个强联通分量有一个点 \(a=1\)，如果有前驱那么我们可以将这一个强联通分量内的点全操作成 \(2\)。

建出图跑一个 tarjan 然后跑一个拓扑排序即可。

对于 \((x,y)=(2,2)\) 的限制，我连了边 \((0,x)\) 和 \((0,y)\)，似乎更好考虑一些。

代码写的有点丑和冗余。

 //code by Emissary
#include<bits/stdc++.h>

#define fi first
#define se second
#define vc vector
#define db double
#define ll long long
#define mk make_pair
#define pb push_back
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

//#define int long long

using namespace std;

namespace IO{
	inline int read(){
		int X=0, W=0; char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(int x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(int x){write(x), putchar(32);}
	inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;

const int MAXN = 5e5+5;

vc<PI> G[MAXN];
vc<int> P[MAXN];

int hd, tl, Q[MAXN], res[MAXN];
int bel[MAXN], du[MAXN], node[MAXN], colcnt;
int n, m, topf, stk[MAXN], dfn[MAXN], low[MAXN], tot;
int head[MAXN], ne[MAXN<<1], to[MAXN<<1], weight[MAXN<<1], cnt;

bool mark[MAXN], ins[MAXN], vis[MAXN], ind[MAXN];

inline void add(int x, int y, int w){++cnt;to[cnt]=y;ne[cnt]=head[x];head[x]=cnt;weight[cnt]=w;}

inline void tarjan(int x){
	stk[++topf]=x; dfn[x]=low[x]=++tot; ins[x]=1;
	for(int i=head[x];i;i=ne[i]){
		if(dfn[to[i]]){
			if(ins[to[i]]) low[x]=min(low[x],dfn[to[i]]);
		}
		else tarjan(to[i]), low[x]=min(low[x],low[to[i]]);
	}	
	if(low[x]==dfn[x]){
		int t; stk[topf+1]=-1; ++colcnt;
		while(stk[topf+1]!=x){
			t=stk[topf];
			ins[t]=0; bel[t]=colcnt; node[colcnt]=t;
			--topf;
		}
	}
	return ;
}

inline void DFS(int x){//这一部分是搜出一个强联通分量内的 dfs 树
	vis[x]=1;
	for(int i=head[x];i;i=ne[i]){
		if(vis[to[i]] || bel[to[i]]!=bel[x]) continue;
		DFS(to[i]); P[bel[x]].pb(weight[i]); ind[weight[i]]=1;
	}
	return ;
}

inline void solve(){
	int a, b, c, d; vc<int> A, B;
	n=read(), m=read(); cnt=0; tot=0; colcnt=0;
	for(int i=0;i<=n;++i) vis[i]=0, dfn[i]=0, du[i]=0, res[i]=0;
	for(int i=0;i<=n;++i) mark[i]=0, head[i]=0, G[i].clear();
	for(int i=1;i<=m;++i){
		a=read(), b=read();
		c=read(), d=read(); ind[i]=0;
		mark[a]=mark[c]=1;
		if(b+d==2) A.pb(i), ind[i]=1;
		if(b+d==3){
			if(d==1) swap(a,c);
			add(a,c,i);
		}
		if(b+d==4) add(0,a,0), add(0,c,0), B.pb(i), ind[i]=1;
	}
	int ans=0; mark[0]=1;
	for(int i=1;i<=n;++i) ans+=mark[i];
	for(int i=0;i<=n;++i){
		if(dfn[i] || !mark[i]) continue;
		tarjan(i);
	}
	for(int i=0;i<=n;++i)
		for(int j=head[i];j;j=ne[j]){
			if(bel[i]!=bel[to[j]]){
				node[bel[to[j]]]=to[j];
				G[bel[to[j]]].pb(mk(bel[i],weight[j]));  du[bel[i]]++; ind[weight[j]]=1; res[bel[to[j]]]++;
			}
		}
	hd=1, tl=0;
	for(int i=1;i<=colcnt;++i) if(du[i]==0) Q[++tl]=i; (ans<<=1);
	for(int i=1;i<=colcnt;++i) if(res[i]==0) ans--; ans++;
	eprint(ans); for(auto i:A) sprint(i);
	for(int i=1;i<=colcnt;++i) P[i].clear(), DFS(node[i]);
	for(int i=1;i<=m;++i) if(ind[i]==0) sprint(i);
	while(hd<=tl){
		int t=Q[hd++];
		for(auto i:P[t]) if(i) sprint(i);//强联通分量内部的边
		for(auto ver:G[t]){
			if(ver.se) sprint(ver.se);//不同强联通分量之间的边
			if((--du[ver.fi])==0) Q[++tl]=ver.fi;
		}
	}
	for(auto i:B) sprint(i); putchar(10);
}

signed main(){
	int t=read();
	while(t--) solve();
	return 0;
}