记录编号	403348	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	0.089 s
提交时间	2017-05-09 21:57:39	内存使用	0.59 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>

using namespace std;

vector<int>e[10100];
queue<int>que;
stack<int>st;

int n,m,inq[10100],dis[10100],a,b,cnt,dfn[10100],low[10100],ins[10100],be[10100],t;
int supert;

void tarjan(int o)
{
	if(dfn[o]) return;
	cnt++;
	dfn[o]=low[o]=cnt;
	st.push(o);
	ins[o]=1;
	for(int i=0;i<e[o].size();i++)
	{
		if(!dfn[e[o][i]])
		{
			tarjan(e[o][i]);
			low[o]=min(low[e[o][i]],low[o]);
		}
		else if(ins[e[o][i]])
		{
			low[o]=min(low[e[o][i]],low[o]);
		}
	}
	if(low[o]==dfn[o])
	{
		t++;
		while(!st.empty()&&st.top()!=o)
		{
			be[st.top()]=t;
			ins[st.top()]=0;
			st.pop();
		}
		if(!st.empty())
		{
			be[st.top()]=t;
			ins[st.top()]=t;
			st.pop();
		}
	}
}

void spfa(int pos)
{
	for(int i=0;i<=n;i++) dis[i]=1e9;
	que.push(pos);
	inq[pos]=1;
	dis[pos]=0;
	while(!que.empty())
	{
		int u=que.front();
		que.pop();
		inq[u]=0;
		int ok=1;
		for(int i=0;i<e[u].size();i++)
		{
			if(be[e[u][i]]!=supert)
			{
				ok=0;
				break;
			}
		}
		if(ok)
		{
			for(int i=0;i<e[u].size();i++)
			{
				if(dis[e[u][i]]>dis[u]+1)
				{
					dis[e[u][i]]=dis[u]+1;
					if(!inq[e[u][i]])
					{
						que.push(e[u][i]);
						inq[e[u][i]]=1;
					}
				}
			}
		}
		
	}
	return;
}

int main()
{
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		low[i]=1e9;
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
	}
	scanf("%d%d",&a,&b);
	e[b].push_back(a);
	for(int i=1;i<=n;i++) tarjan(i);
	supert=be[b];
	e[b].pop_back();
	spfa(a);
	if(dis[b]==1e9) printf("-1");
	else printf("%d",dis[b]);
	return 0;
}
/*
3 2
1 2
2 1
1 3


6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
*/