Pagini recente » Cod sursa (job #2755367) | Cod sursa (job #536784) | Cod sursa (job #3128316) | Cod sursa (job #1498294) | Cod sursa (job #3030222)
#include <iostream>
#include <vector>
#include <set>
#include <fstream>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int maxN = 1e5 + 5;
vector <int> g[maxN];
vector <pair<int,int>> muchii;
set <int> comp[maxN];
int T[maxN], minT[maxN], vizit[maxN];
int timp = 0, CB = 0;
void comp_noua (int node, int to) {
CB++;
while(true) {
int a = muchii.back().first, b = muchii.back(). second;
muchii.pop_back();
comp[CB].insert(a);
comp[CB].insert(b);
if(node == a && to == b)
return ;
}
}
void dfs (int node, int dad = -1) {
T[node] = ++timp;
minT[node] = timp;
vizit[node] = true;
for(int to : g[node]) {
if(to == dad)
continue;
if(vizit[to] == true && minT[node] > T[to]) {
minT[node] = T[to];
}
if(vizit[to] == false) {
muchii.push_back({node, to});
dfs(to, node);
minT[node] = min(minT[node], minT[to]);
if(T[node] <= minT[to]) {
comp_noua(node, to);
}
}
}
}
signed main() {
int n, m; fin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v; fin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
fout << CB << '\n';
for(int i = 1; i <= CB; i++, fout << '\n')
for(int j : comp[i])
fout << j << " ";
return 0;
}