Pagini recente » Cod sursa (job #1157030) | Cod sursa (job #2076155) | Cod sursa (job #149966) | Cod sursa (job #2148239) | Cod sursa (job #2013675)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
const int MAX_M = 200000;
struct Edge {
int a, b;
int other(int nod) {
return a ^ b ^ nod;
}
} e[MAX_M];
vector<int> graph[1+MAX_N];
int low[1+MAX_N], h[1+MAX_N];
vector<vector<int> > comp;
int st[MAX_M], top;
int min(int a, int b) {
if(a < b)
return a;
return b;
}
void dfs(int nod, int fatherEdge) {
for(auto it: graph[nod]) {
int son = e[it].other(nod);
if(low[son] == 0) {
low[son] = h[son] = h[nod] + 1;
st[top++] = it;
dfs(son, it);
low[nod] = min(low[nod], low[son]);
if(low[son] >= h[nod]) {
vector<int> bic;
int last;
do {
last = st[--top];
bic.push_back(e[last].a);
bic.push_back(e[last].b);
} while(last != it);
sort(bic.begin(), bic.end());
bic.resize(unique(bic.begin(), bic.end()) - bic.begin());
comp.push_back(bic);
}
} else if(it != fatherEdge)
low[nod] = min(low[nod], h[son]);
}
}
int main() {
int n, m;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin >> n >> m;
for(int i = 0; i < m; ++i) {
fin >> e[i].a >> e[i].b;
graph[e[i].a].push_back(i);
graph[e[i].b].push_back(i);
}
low[1] = h[1] = 1;
dfs(1, -1);
fout << comp.size() << '\n';
for(auto it: comp) {
for(int i = 0; i < it.size(); ++i)
fout << it[i] << ' ';
fout << '\n';
}
return 0;
}