模板题——求割点与桥
题意,要使一个无向图不连通,输出必定要删掉的边的数量及其编号。求桥的裸题,可拿来练手。
套模板的时候注意本题两节点之间可能有多条边,而模板是不判重边的,所以直接套模板的话,会将重边也当做桥输出,因此要在判断桥的时候加一个判断,即当且仅当两点之间仅有一条边,且满足dfn[cur] < low[i],(cur, i)才是桥。
另外本题节点数为105,用邻接矩阵的话会内存超限,所以我用了了一个multiset存储边及其编号。
代码如下:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAX_V = ;
const int MAX_E = ;
struct Edge
{
int to, id;
Edge() {}
Edge(int _t, int _i):to(_t), id(_i) {}
bool operator < (const Edge& rhs) const
{
return to < rhs.to;
}
};
multiset<Edge> edge[MAX_V];
multiset<int> tms[MAX_V];
vector<int> ans;
int vis[MAX_V]; //结点v当前访问状态,0表示未访问,1表示在栈中,2表示已经访问过
int dfn[MAX_V]; //结点v被访问时的深度
int low[MAX_V]; //结点v可以到达的访问时间最早的祖先的深度
void cut_bridge(int cur, int father, int dep, int n) //vertex: 0~n-1
{
vis[cur] = ;
dfn[cur] = dep;
low[cur] = dep;
int children = ;
int sz = edge[cur].size();
for(multiset<Edge>::iterator it = edge[cur].begin(); it != edge[cur].end(); it++)
{
int id = (*it).id;
int i = (*it).to;
if(i != father && vis[i] == ) //i在当前栈中,说明图中有一个环,用i的深度更新cur的low值;
{
if(dfn[i] < low[cur]) low[cur] = dfn[i]; //将结点cur可以到达的访问时间最早的祖先的深度更新为结点i被访问时的深度;
}
if(vis[i] == ) //i没被访问过,递归访问节点i,并用i的可以到达的最早祖先来更新cur的low值;
{
cut_bridge(i, cur, dep+, n);
if(low[i] < low[cur]) low[cur] = low[i];
if(low[i] > dfn[cur] && tms[cur].count(i) == )
{
ans.push_back(id);
}//判断桥
}
}
vis[cur] = ;
}
void init(int n)
{
ans.clear();
memset(vis, , sizeof(vis));
for(int i = ; i <= n; i++)
{
edge[i].clear();
tms[i].clear();
}
}
int main()
{
int T;
scanf("%d", &T);
for(int kase = ; kase < T; kase++)
{
if(kase) printf("\n");
int n, m;
scanf("%d%d", &n, &m);
init(n);
for(int i = ; i < m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
Edge e1(v, i+), e2(u, i+);
edge[u].insert(e1);
edge[v].insert(e2);
tms[u].insert(v);
tms[v].insert(u);
}
for(int i = ; i <= n; i++)
if(vis[i] == )
cut_bridge(i, -, , n); sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for(int i = ; i < ans.size(); i++)
{
if(i) printf(" ");
printf("%d", ans[i]);
}
if(ans.size()) printf("\n");
}
return ;
}
ZOJ 2588