榆树市住房和城乡建设局网站,查看网站备案,阿里云万网域名查询,今科网站建设公司题目描述 因为某国被某红色政权残酷的高压暴力统治。美国派出将军uim#xff0c;对该国进行战略性措施#xff0c;以解救涂炭的生灵。 该国有n个城市#xff0c;这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。 uim发现有些铁路被毁坏之后#xff0c;某… 题目描述 因为某国被某红色政权残酷的高压暴力统治。美国派出将军uim对该国进行战略性措施以解救涂炭的生灵。 该国有n个城市这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。 uim发现有些铁路被毁坏之后某两个城市无法互相通过铁路到达。这样的铁路就被称为key road。 uim为了尽快使该国的物流系统瘫痪希望炸毁铁路以达到存在某两个城市无法互相通过铁路到达的效果。 然而只有一发炮弹美国国会不给钱了。所以他能轰炸哪一条铁路呢 输入输出格式 输入格式 第一行nm(1n150, 1m5000)分别表示有n个城市总共m条铁路。 以下m行,每行两个整数a, b表示城市a和城市b之间有铁路直接连接。 输出格式 输出有若干行。 每行包含两个数字a,b(a b)表示 a,b 是key road。 请注意输出时所有的数对 a,b 必须按照a从小到大排序输出如果a相同则根据b从小到大排序。 输入输出样例 输入样例1 6 6 1 2 2 3 2 4 3 5 4 5 5 6 输出样例1 1 2 5 6 求割边模板题直接用Tarjan (我把我博客里tarjan求割边的模板代码改改拿过来了) code #includecstdio
#includeiostream
#includealgorithm
using namespace std;const int MAX1000010;
int n,m,cnt,sum;
int head[MAX],low[MAX],dfn[MAX],cedge[MAX];struct edg{int to,next,from;
}edge[MAX];void add(int x,int y){edge[cnt].nexthead[x];edge[cnt].fromx,edge[cnt].toy;head[x]cnt;
}void cutedge(int u,int f){dfn[u]low[u]cnt;for(int ihead[u];i;iedge[i].next){int vedge[i].to;if(!dfn[v]){cutedge(v,u);low[u]min(low[u],low[v]);if(dfn[u]low[v]) cedge[sum]i;}else if(v!f) low[u]min(low[u],dfn[v]);}
}bool cmp(int a,int b){if(edge[a].fromedge[b].from) return edge[a].toedge[b].to;return edge[a].fromedge[b].from;
}void find_cutedge(){for(int i1;in;i) if(!dfn[i]) cutedge(i,0);sort(cedge1,cedgesum1,cmp);for(int i1;isum;i) printf(%d %d\n,edge[cedge[i]].from,edge[cedge[i]].to);
}int main(){scanf(%d %d,n,m);for(int i1;im;i){int a,b;scanf(%d %d,a,b);add(a,b);add(b,a);}find_cutedge();return 0;
} 转载于:https://www.cnblogs.com/Menteur-Hxy/p/9248045.html
