记录编号	486063	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	snake	是否通过	通过
代码语言	C++	运行时间	0.085 s
提交时间	2018-02-05 09:51:07	内存使用	4.04 MiB

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAX=10010;
const int MAXm=400010;

int sumout[MAX];    //各个点的出度
int sumin[MAX]; //各个点的(反向bfs时的)入度
//当sumout[i]>sumin[i]时点不可用

struct uf
{
	private:
	int size[MAX];
	int f[MAX];
	int num;
	
	public:
	uf(int n)
	{
		num=n;
		for(int i=1;i<=num;i++)
		{
			size[i]=1;
			f[i]=i;
		}
	}
	
	int find(int a)
	{
		if(f[a]!=a) f[a]=find(f[a]);
		return f[a];
	}
	
	void join(int a,int b)
	{
		int fa=find(a);
		int fb=find(b);
		if(fa==fb) return;
		if(size[fa]>size[fb]){f[fb]=fa;size[fa]+=size[fb];}
		else{f[fa]=fb;size[fb]+=size[fa];}
		num--;
		return;
	}
	
	bool check(int a,int b){return find(a)==find(b);}
	
	int cal(void){return num;}
};

struct edge
{
	int to;
	edge* next;
	bool exists;    //exists==true时不是反向边
	
	edge()
	{
		to=0;
		next=NULL;
		exists=0;
	}
}e[MAXm];

edge* head[MAX];
int k=1;
bool visited[MAX];
int dep[MAX];

void bfs_backward(int s)
{
	//memset(visited,0,sizeof(visited));
	queue<int> q;
	q.push(s);
	visited[s]=1;
	while(!q.empty())
	{
		int& t=q.front();
		q.pop();
		edge* tar=head[t];
		while(tar!=NULL)
		{
			if(!visited[tar->to] && !tar->exists)
			{
				visited[tar->to]=1;
				q.push(tar->to);
			}
			if(!tar->exists) sumin[tar->to]++;
			tar=tar->next;
		}
	}
	return;
}

void bfs_forward(int s)
{
	memset(visited,0,sizeof(visited));
	queue<int> q;
	q.push(s);
	//visited[s]=1;
	dep[s]=1;
	while(!q.empty())
	{
		int& t=q.front();
		q.pop();
		edge* tar=head[t];
		while(tar!=NULL)
		{
			if(tar->exists && sumin[tar->to]>=sumout[tar->to] && (!dep[tar->to] || dep[t]+1<dep[tar->to]))
			{
				dep[tar->to]=dep[t]+1;
				q.push(tar->to);
			}
			tar=tar->next;
		}
	}
	return;
}

int main()
{
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
	int n,m,x,y,s,t;
	scanf("%d%d",&n,&m);
	uf form(n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		if(x==y) continue;
		form.join(x,y);
		e[k].exists=1;
		e[k].next=head[x];
		e[k].to=y;
		head[x]=&e[k++];
		e[k].exists=0;
		e[k].next=head[y];
		e[k].to=x;
		head[y]=&e[k++];
		sumout[x]++;
	}
	scanf("%d%d",&s,&t);
	if(!form.check(s,t)){printf("-1\n");return 0;}
	bfs_backward(t);
	bfs_forward(s);
	if(dep[t]) printf("%d\n",dep[t]-1);
	else printf("-1\n");
	return 0;
}
/*
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
*/