网站建设与企业管理心得体会,便民信息微信平台推广,网站怎么做下拉刷新,中国空间站合作国家名单题干#xff1a;
给出一个无向图G的顶点V和边E。进行Q次查询#xff0c;查询从G的某个顶点V[s]到另一个顶点V[t]#xff0c;是否存在2条不相交的路径。#xff08;两条路径不经过相同的边#xff09;
#xff08;注#xff0c;无向图中不存在重边#xff0c;也就是说…题干
给出一个无向图G的顶点V和边E。进行Q次查询查询从G的某个顶点V[s]到另一个顶点V[t]是否存在2条不相交的路径。两条路径不经过相同的边
注无向图中不存在重边也就是说确定起点和终点他们之间最多只有1条路 收起
输入
第1行2个数M N中间用空格分开M是顶点的数量N是边的数量。2 M 25000, 1 N 50000)
第2 - N 1行每行2个数中间用空格分隔分别是N条边的起点和终点的编号。例如2 4表示起点为2终点为4由于是无向图所以从4到2也是可行的路径。
第N 2行一个数Q表示后面将进行Q次查询。(1 Q 50000)
第N 3 - N 2 Q行每行2个数s, t中间用空格分隔表示查询的起点和终点。
输出
共Q行如果从s到t存在2条不相交的路径则输出Yes否则输出No。
输入样例
4 4
1 2
2 3
1 3
1 4
5
1 2
2 3
3 1
2 4
1 4
输出样例
Yes
Yes
Yes
No
No
解题报告 直接Tarjan。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
vectorint vv[MAX];
int n,m;
int DFN[MAX],LOW[MAX],stk[MAX];
bool vis[MAX];
int f[MAX];
int clk,index;
void tarjan(int x,int rt) {DFN[x] LOW[x] clk;vis[x] 1;stk[index] x;for(int v : vv[x]) {if(v rt) 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]) {while(1) {int tmp stk[index--];vis[tmp]0;f[tmp]x;if(tmp x) break;}}
}int main() {cinnm;for(int i 1; in; i) f[i]i;for(int a,b,i 1; im; i) {scanf(%d%d,a,b);vv[a].pb(b);vv[b].pb(a);}for(int i 1; in; i) {if(!DFN[i]) tarjan(i,-1);}int q;cinq;while(q--) {int a,b;scanf(%d%d,a,b);if(f[a] f[b]) printf(Yes\n);else printf(No\n);}return 0 ;
}其实对于无向图就很简单了因为 void tarjan(int x,int rt) {DFN[x] LOW[x] clk;vis[x] 1;stk[index] x;for(int v : vv[x]) {if(v rt) 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]);else printf(132123123);} }if(DFN[x] LOW[x]) {while(1) {int tmp stk[index--];vis[tmp]0;f[tmp]x;if(tmp x) break;}}
}
这样写也能过总之对于一个无向图就是怎么写都可以过所以就随便写就行了。总之一个结论对于一个无向图是不存在DFN过但是不在栈内的也就是对于一个联通分量能搜到的点肯定全搜完了才会返回到main函数但是虽然一个联通分量中的带你都能搜的到但是是否成环这就是另一个问题了。
