割邊模板
// 無向雙連通例子.cpp : 此文件包含 "main" 函數。程序執行將在此處開始并結束。
//
/*
http://oj.daimayuan.top/course/23/problem/983
給一個n個點m條邊的無向連通圖,從小到大輸出所有割邊的編號。注意:邊從1開始標號。
輸入格式
第一行包含兩個數n,m(1≤n≤105,1≤m≤2×105)。
接下來m行,每行兩個整數u,v表示一條無向邊,沒有自環,但可能有重邊。
輸出格式
首先輸出一個整數,表示割邊個數。接下來一行,若干個從小到大的數,表示割邊的編號。
樣例輸入
7 8
1 2
2 3
3 4
2 5
4 5
5 6
5 7
5 7
樣例輸出
2
1 6
*/
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n, m;
const int N = 100010, M = 400010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
bool bridge[M];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u,int from) {
dfn[u] = low[u] = ++timestamp;
stk[++top] = u;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j, i);
low[u] = min(low[u], low[j]);
if (dfn[u] < low[j]) {
bridge[i] = bridge[i ^ 1] = true;
}
}
else if (i != (from ^ 1))
low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u]) {
++dcc_cnt;
int y;
do {
y = stk[top--];
id[y] = dcc_cnt;
} while (y != u);
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i= 0;i < m;i++){
int a, b;
cin >> a >> b;
add(a, b); add(b, a);
}
//tarjan(1,-1);
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i, -1);
}
vector<int> ans;
for (int i = 1; i <= m; i++) {
if (bridge[(i-1)* 2]) {
ans.push_back(i);
}
}
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}
// 無向雙連通例子.cpp : 此文件包含 "main" 函數。程序執行將在此處開始并結束。
//
/*
http://oj.daimayuan.top/course/23/problem/983
給一個n個點m條邊的無向連通圖,從小到大輸出所有割邊的編號。注意:邊從1開始標號。
輸入格式
第一行包含兩個數n,m(1≤n≤105,1≤m≤2×105)。
接下來m行,每行兩個整數u,v表示一條無向邊,沒有自環,但可能有重邊。
輸出格式
首先輸出一個整數,表示割邊個數。接下來一行,若干個從小到大的數,表示割邊的編號。
樣例輸入
7 8
1 2
2 3
3 4
2 5
4 5
5 6
5 7
5 7
樣例輸出
2
1 6
*/
#include <iostream>
#include <vector>
using namespace std;
const int SIZE = 200010;
int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
int dfn[SIZE], low[SIZE], n, m, tot, num;
bool bridge[SIZE * 2];
void add(int x, int y) {
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void tarjan(int x, int in_edge) {
dfn[x] = low[x] = ++num;
for (int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if (!dfn[y]) {
tarjan(y, i);
low[x] = min(low[x], low[y]);
if (low[y] > dfn[x]) {
bridge[i] = bridge[i ^ 1] = true;
}
}
else if(i != (in_edge^1)) {
low[x]=min(low[x],dfn[y]);
}
}
}
int main()
{
cin >> n >> m;
tot = 1;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
add(x, y); add(y, x);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i, 0);
}
vector<int> ans;
for (int i = 2; i < tot; i += 2) {
if (bridge[i]) {
ans.push_back(i / 2);
}
}
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}
作 者: itdef
歡迎轉帖 請保持文本完整并注明出處
技術博客 http://www.rzrgm.cn/itdef/
B站算法視頻題解
https://space.bilibili.com/18508846
qq 151435887
gitee https://gitee.com/def/
歡迎c c++ 算法愛好者 windows驅動愛好者 服務器程序員溝通交流
如果覺得不錯,歡迎點贊,你的鼓勵就是我的動力
歡迎轉帖 請保持文本完整并注明出處
技術博客 http://www.rzrgm.cn/itdef/
B站算法視頻題解
https://space.bilibili.com/18508846
qq 151435887
gitee https://gitee.com/def/
歡迎c c++ 算法愛好者 windows驅動愛好者 服務器程序員溝通交流
如果覺得不錯,歡迎點贊,你的鼓勵就是我的動力
浙公網安備 33010602011771號