51nod1072 求解一个图里面的强联通分量

蔚落 2022-08-22 03:51 136阅读 0赞

给出一个无向图G的顶点V和边E。进行Q次查询，查询从G的某个顶点V\[s\]到另一个顶点V\[t\]，是否存在2条不相交的路径。（两条路径不经过相同的边）

（注，无向图中不存在重边，也就是说确定起点和终点，他们之间最多只有1条路）

这个题目，我们看到是一个无向图。可以转换成有向图之后再来处理。我们可以想到，两个点因为本来是无向的转化成有向的之后，那么看有没有两条不相交的路径就是看这两个点是否在一个强联通分量中。

所以这个题目就变成求强连通分量了。

用tarjan算法。

百度百科解释的很清楚[点击打开链接][Link 1]

#include<iostream>
    #include<stdio.h>
    #include<algorithm>
    #include<vector>
    #include<cstring>
    using namespace std;
    
    const int maxn = 50010;
    int Stack[maxn];  //每遍历一个点便入栈
    int top;
    bool inStack[maxn]; //判断某个点是否已经在栈里面
    int dfn[maxn],low[maxn];
    //这两个数组最为关键
    //dfn(u)为节点u搜索的次序编号(时间戳)，
    //Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号
    int beLong[maxn];//判断哪些点联通
    int Bcnt, Dindex; //记录强连通的个数和当前时间
    vector<int> v[maxn]; //邻接表保存边
    
    int n,m,q;
    
    void Init()
    {
    	Bcnt=Dindex=top=0;
    	memset(dfn,-1,sizeof(dfn));
    	memset(inStack,false,sizeof(inStack));
    	for(int i=0;i<maxn;i++) v[i].clear();
    }
    
    void tarjan(int u,int fa)
    {
    	dfn[u]=low[u]=++Dindex;
    	Stack[++top]=u;
    	inStack[u]=true;
    
    	int u_size=v[u].size();
    	for(int i=0;i<u_size;i++)
    	{
    		int k=v[u][i];
    		if(dfn[k]==-1)
    		{//没有访问过
    			tarjan(k,u);
    			low[u]=min(low[u],low[k]);
    		}
    		else if(inStack[k]&&k!=fa)
    			low[u]=min(low[u],dfn[k]);
    	}
    	if(dfn[u]==low[u])
    	{
    		Bcnt++;
    		int tmp;
    		do
    		{
    			tmp=Stack[top--];
    			beLong[tmp]=Bcnt;
    			//printf("bcnt = %d v = %d\n", Bcnt, tmp);
    			inStack[tmp]=false;
    		}while(tmp!=u);
    		//printf("\n");
    	}
    }
    
    void Solve()
    {
    	for(int i=1;i<=n;i++)
    		if(dfn[i]==-1)
    			tarjan(i,-1);
    }
    
    int main()
    {
    	Init();
    	//scanf("%d%d",&n,&m);
    	cin>>n>>m;
    	for(int i=0;i<m;i++)
    	{
    		int a,b;
    		//scanf("%d%d",&a,&b);
    		cin>>a>>b;
    		v[a].push_back(b);
    		v[b].push_back(a);
    	}
    	Solve();
    	//scanf("%d",&q);
    	cin>>q;
    	while(q--)
    	{
    		int x,y;
    		//scanf("%d%d",&x,&y);
    		cin>>x>>y;
    		if(beLong[x]==beLong[y])
    			puts("Yes");
    			//printf("Yes\n");
    		else
    			puts("No");
    			//printf("No\n");
    	}
    	return 0;
    }

[Link 1]: http://baike.baidu.com/link?url=GlW7eGhZxby26vYJzlNSpANKBLToiwx-Fhvu_NxEXuUymVjQxZXk_SAkq8VVMg2UhXGXSUo4luQddo2ZNESX6_