西安网站制作公司官网,wordpress去除文章rss,做网站服务好,wordpress和phpmyadmin题目描述 小A和小B在一个无向图G上进行一个游戏。图G是连通的#xff0c;有n个点#xff0c;n条边#xff0c;无重边#xff0c;无自环#xff0c;结点编号为1~n。游戏开始前小A在结点x#xff0c;小B在结点y#xff08;x≠y#xff09;。游戏开始后#xff0c;小A和小… 题目描述 小A和小B在一个无向图G上进行一个游戏。图G是连通的有n个点n条边无重边无自环结点编号为1~n。游戏开始前小A在结点x小B在结点yx≠y。游戏开始后小A和小B轮流进行移动小A先移动每次移动可以从当前结点移动到与当前结点相邻的某个结点。小A的目标是抓到小B某一次移动之后小A与小B在同一个结点小B的目标是不被小A抓到。两人都有图G的地图并且知道对方在哪个结点两人都采取最优策略问小A是否能通过有限次移动抓到小B。 输入描述 第1行3个整数n、x、y 第2~n1行每行2个整数u、v代表u与v之间有边相连。 输出描述 若小A能通过有限次移动抓到小B输出1否则输出0。 数据范围 n≤100000 样例输入 10 2 4
1 2
1 3
2 4
1 5
5 6
1 7
5 8
6 9
3 10
8 10 样例输出 1 题解这是一个树并且这个树上存在且存在一个环。
1.当A和B之间距离为1或0的时候直接输出1。
2.否则的话当环的长度小于等于3的时候直接输出1因为B一定会被A捉到。
3.我们进行双连通分量的缩点将环缩成一个点下面我们判断当A、B同属于一个环上的时候直接输出0因为B绕着环跑永远不会被捉到。
4.然后我们从环缩成的点开始进行dfs序遍历得到每一个点到基环的距离如果dis[belong[x]] 1 dis[belong[y]]表明A距离基环更近直接输出1否则输出0.
代码 #include bits/stdc.h
using namespace std;
const int MAXN 1e510;
int head[MAXN];
int cnt;
struct edge{ int v; int next; int cost;
}Es[MAXN1];
void init(){ cnt 0; memset(head,-1,sizeof(head));
}
inline void add_edge(int i,int j,int cost){ Es[cnt].v j; Es[cnt].cost cost; Es[cnt].next head[i]; head[i] cnt;
}
int n,x,y;
int DFN[MAXN],LOW[MAXN];
int stk[MAXN],vis[MAXN],belong[MAXN];
int idx,sccnum,tot;
vectorint scc[MAXN];
void tarjan(int x,int fa){DFN[x] LOW[x] tot;stk[idx] x;vis[x] 1;for(int e head[x];e ! -1;e Es[e].next){int v Es[e].v;if(v fa) continue;if(!DFN[v]){tarjan(v,x);LOW[x] min(LOW[x],LOW[v]);}else if(vis[v]){LOW[x] min(LOW[x],DFN[v]);}}if(DFN[x] LOW[x]){sccnum;int item;do{item stk[idx--];belong[item] sccnum;scc[sccnum].push_back(item);vis[item] 0;}while(x ! item);}
}
int dis[MAXN];
int vis2[MAXN];
void dfs(int x,int dep){dis[x] dep;for(int i 0;i scc[x].size();i){int u scc[x][i];for(int e head[u];e ! -1;e Es[e].next){int v Es[e].v;if(!vis2[belong[v]]){vis2[belong[v]] 1;dfs(belong[v],dep1);}}}
}
int main(){init();scanf(%d%d%d,n,x,y);if(x y) {puts(1);return 0;}for(int i 0;i n;i){int a,b;scanf(%d%d,a,b);add_edge(a,b,1);add_edge(b,a,1);}for(int e head[x];e ! -1;e Es[e].next){int v Es[e].v;if(v y){puts(1);return 0;}}tarjan(1,0);int start 0;for(int i 1;i sccnum;i){if(scc[i].size() 3){start i;}}if(!start){puts(1);return 0;}if(belong[x] belong[y]){puts(0);return 0;}dfs(start,0);if(dis[belong[x]] 1 dis[belong[y]]){puts(1);}else{puts(0);}return 0;
}
/*
7 4 1
1 2
2 3
3 4
4 5
5 6
6 7
7 4
*/
