HDU--Railway(Tarjan算法)

原题链接

每个路线相当于一张连通图

无向图中存在余边的情况即为点数<边数

有冲突的路线即存在属于多个路线即该条路为两个连通图中间的桥

#include 
#include 
#include 
#include
#include using namespace std;
const int N = 10010,M=200010;
typedef pair PII;
int h[N], e[M], ne[M], idx;//邻接表存图
int n,m,a,b,res;//res存桥的个数
int low[N],num[N],times,sto;
int orz[N];//存某个连通图中的边数
int p[N];//用来记录割点所属的对应的连通图的编号(表示该点为割点且编号为其值，值用以求边数点数)
set pos[N];//存编号为i的连通图中包含的点数
stack op;
void add(int a, int b)  //邻接表加边
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void init()//初始化
{memset(h, -1, sizeof h);memset(low,0,sizeof low); memset(num,0,sizeof num);memset(p,0,sizeof p);memset(orz,0,sizeof orz);res=idx=times=sto=0;while(op.size())op.pop();
}
void dfs(int u,int fa)
{low[u]=num[u]=++times;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(!num[j]){op.push({u,j});dfs(j,u);low[u]=min(low[u],low[j]);if(low[j]>num[u])res++;//存在桥if(low[j]>=num[u]){//存在割点sto++;p[u]=sto;pos[sto].clear();while(1){auto t=op.top();op.pop();orz[sto]++;pos[sto].insert(t.first),pos[sto].insert(t.second);if(u==t.first&&j==t.second)break;}}}else if(num[j]pos[i].size())ans+=orz[i];}cout<>n>>m,n||m){init(); for(int i=1;i<=m;i++){cin>>a>>b;add(a+1,b+1),add(b+1,a+1);//给出的u，v为[0,n)，处理使得u，v--[1,n]}Tarjan();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！