在尼谷AC了,但被校内数据hack了
查看原帖
在尼谷AC了,但被校内数据hack了
1072786
jq_ll19802楼主2024/7/17 14:31

帮忙看看有什么问题?

#include<bits/stdc++.h>
using namespace std;

int n,m,id,idx,head[10005];
 
int dfn[8005],low[8005],sk[100005],top,wi,w[100005]; 

string a[4005],b[4005],c,d;

map<string,int>qn,ql;

bool daan[100005];

struct ff
{
	int v,next;
}edge[100005];

void ci(int x,int y)
{
	edge[++idx].v=y;
	edge[idx].next=head[x];
	head[x]=idx;
	
}

void tarjan(int x)
{
	dfn[x]=low[x]=++id;
	sk[++top]=x;
	
	for(int i=head[x];i;i=edge[i].next)
	{
		if(w[edge[i].v]==0)
		{
			if(dfn[edge[i].v]==0)
			{
				tarjan(edge[i].v);
				low[x]=min(low[x],low[edge[i].v]);
			}
			else low[x]=min(low[x],dfn[edge[i].v]);
		}
	}
	if(dfn[x]==low[x])
	{
		wi++;
		int op=0;
		while(1)
		{
			w[sk[top]]=wi;
			op++;
			if(sk[top]==x)
			{
				top--;
				break;
			}
			top--;
		}
		if(op>1)daan[wi]=true;
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
    {
    	cin>>a[i]>>b[i];
    	ql[a[i]]=i,qn[b[i]]=i;
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
    	cin>>c>>d;
    	ci(ql[c],qn[d]);
    }
    for(int i=1;i<=n;i++)
    {
    	if(dfn[i]==0)
    	{
    		tarjan(i);
    	}
    }
    for(int i=1;i<=n;i++)
    {
    	if(daan[w[i]])
    	{
    		cout<<"Unsafe\n";
    	}
    	else
    	cout<<"Safe\n";
    }
    return 0;
}
2024/7/17 14:31
加载中...