Pagini recente » Cod sursa (job #2286650) | Cod sursa (job #3243868) | Cod sursa (job #582685) | Cod sursa (job #1260167) | Cod sursa (job #3197798)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMAX = 100005;
const int MMAX = 200005;
vector <int> sol;
vector <vector <int>> afis;
vector <int> g[NMAX];
int highest[NMAX];
int depth[NMAX];
void build( int node){
vector<int> bicon;
while( !sol.empty() && sol.back() != node ){
bicon.push_back(sol.back());
sol.pop_back();
}
bicon.push_back(node);
//sol.pop_back();
afis.push_back(bicon);
}
void tarjan( int node, int level, int tata ){
sol.push_back(node);
highest[node] = level;
depth[node] = level;
for( auto next : g[node] ){
if( next == tata )
continue;
if( !depth[next] ){
tarjan(next, level+1, node);
highest[node] = min(highest[next], highest[node]);
if( highest[next] >= level ) {
build(node);
// cout << node << ' ';
}
}
else
highest[node] = min(highest[next], highest[node]);
}
}
int main()
{
int n, m;
in >> n >> m;
for( int i = 0; i < m; i++ ){
int a, b;
in >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
tarjan( 1, 1, 0);
// for (int i = 1; i <= n; i++) {
// cout << highest[i] << ' ';
// }
// cout << '\n';
out << afis.size() << "\n";
for( int i = 0; i < afis.size() ; i++ ){
for( int node: afis[i] )
out << node << " ";
out << "\n";
}
return 0;
}