萌新の智障错误(40分)
查看原帖
萌新の智障错误(40分)
401461
Augury楼主2023/1/31 10:25

码风奇怪,请不要嫌弃

#include<bits/stdc++.h>
#define f(x) (x=='h')
using namespace std;
const int maxn=210;
int n,m;
int dfn[maxn],low[maxn],col[maxn];
bool vis[maxn];
stack<int>st;
int cnt=0,clr=0;
vector<int>g[maxn];
void tarjan(int now){
	dfn[now]=low[now]=++cnt;
	vis[now]=1;
	st.push(now);
	for(int i=0;i<(int)g[now].size();i++){
		int nxt=g[now][i];
		if(!dfn[nxt]){
			tarjan(nxt);
			low[now]=min(low[now],low[nxt]);
		}
		else if(vis[nxt])low[now]=min(low[now],dfn[nxt]);
	}
	if(dfn[now]==low[now]){
		clr++;
		int tmp=-1;
		while(tmp!=now){
			tmp=st.top();
			st.pop();
			col[tmp]=clr;
			vis[tmp]=1;
		}
	}
}
void init(){
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(col,0,sizeof(col));
	for(int i=1;i<=n<<1;i++)g[i].clear();
	cnt=clr=0;
}
void real_main(){
	scanf("%d%d",&n,&m);
	init();
	for(int i=1;i<=m;i++){
		char a,c;
		int b,d;
		cin>>a>>b>>c>>d;
		g[b+(!f(a))*n].push_back(d+f(c)*n);
		g[d+(!f(c))*n].push_back(b+f(a)*n);
	}
	for(int i=1;i<=n<<1;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++){
		if(col[i]==col[i+n]){
			cout<<"BAD\n";
			return;
		}
	}
	cout<<"GOOD\n";
	return;
}
int main(){
	int K;
	scanf("%d",&K);
	while(K--)real_main();
}

再上面的 tarjan 中,节点出栈后应该将 vis[now]=0 ,然鹅蒟蒻写成了 vis[now]=110040100\rightarrow 40

2023/1/31 10:25
加载中...