Pagini recente » Cod sursa (job #1616058) | Cod sursa (job #3141585) | Cod sursa (job #1405976) | Cod sursa (job #3225631) | Cod sursa (job #3219806)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int N = 1e5;
int dist[N + 10], viz[N + 10], distMin[N + 10];
vector <int> g[N + 10];
vector <int> bi[N + 10];
stack <int> st;
int comp;
void dfs (int node, int par ) {
st.push(node);
dist[node] = dist[par] + 1;
distMin[node] = dist[node];
viz[node] = 1;
for ( int i = 0; i < g[node].size(); i++ ) {
if ( g[node][i] != par ) {
if ( viz[g[node][i]] == 0 ) {
dfs ( g[node][i], node );
distMin[node] = min ( distMin[node], distMin[g[node][i]] );
if ( distMin[g[node][i]] >= dist[node] ) {
comp++;
while ( !st.empty() && st.top() != g[node][i] ) {
bi[comp].push_back( st.top() );
st.pop();
}
bi[comp].push_back (st.top());
st.pop();
bi[comp].push_back (node);
}
}
else
distMin[node] = min ( distMin[node], dist[g[node][i]] );
}
}
}
int main () {
int n, m, x, y;
fin >> n >> m;
for ( int i = 0; i < m; i++ ) {
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 0);
fout << comp << "\n";
for ( int i = 1; i <= comp; i++ ) {
for ( int j = 0; j < bi[i].size(); j++ )
fout << bi[i][j] << " ";
fout << "\n";
}
return 0;
}