Pagini recente » Cod sursa (job #2325842) | Cod sursa (job #2721724) | Cod sursa (job #950495) | Cod sursa (job #2946929) | Cod sursa (job #2292146)
#include <stdio.h>
#include <stack>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef pair<int,int> muchie;
const int NMAX = 100005;
const int MMAX = 200005;
vector<vector<int>> G;
vector<int> low;
vector<int> id;
stack<muchie> st;
int N,M;
int ix = 0;
vector<set<int>> sol;
void dfs(int at, int from) {
low[at] = id[at] = ix++;
for (auto node : G[at]) {
if (node == from) {
continue;
}
if (id[node] == -1) {
st.push(make_pair(at, node));
dfs(node, at);
low[at] = min(low[at], low[node]);
if (low[node] >= id[at]) {
set<int> bc;
while (!st.empty()) {
muchie p = st.top();
st.pop();
int n1 = p.first;
int n2 = p.second;
bc.insert(n1);
bc.insert(n2);
if ((n1 == at && n2 == node)) {
break;
}
}
sol.push_back(bc);
}
} else {
low[at] = min(low[at], id[node]);
}
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &N, &M);
low = vector<int>(N+1, 0);
id = vector<int>(N+1, -1);
G = vector<vector<int>>(N+1);
for (int i = 0; i < M; ++i) {
int x,y;
scanf("%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1, -1);
printf("%d\n", int(sol.size()));
for (auto bc : sol) {
for (auto elm : bc) {
printf("%d ", elm);
}
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}