Pagini recente » Cod sursa (job #229928) | Cod sursa (job #387964) | Cod sursa (job #40079) | Cod sursa (job #1487780) | Cod sursa (job #1708665)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define NMAX 100009
#define x first
#define y second
using namespace std;
typedef pair<int, int> edge;
int N, M, T[ NMAX ], order, found[ NMAX ], low[ NMAX ];
vector< int > G[ NMAX ];
vector< vector<int> > bcc;
stack<edge> st;
template<class T>
void makeUnique(vector<T> &v){
sort(v.begin(), v.end());
v.erase( unique( v.begin(), v.end() ), v.end());
}
void getBCC(edge e) {
vector<int> v;
edge aux;
do{
aux = st.top();
v.push_back( aux.x );
v.push_back( aux.y );
st.pop();
}while(aux != e);
makeUnique( v );
bcc.push_back( v );
}
void DFS(int node) {
found[ node ] = low[ node ] = ++order;
int children;
for (vector<int>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
if (!T[ *it ]) {
++children;
T[ *it ] = node;
st.push( edge(node, *it) );
DFS( *it );
low[ node ] = min(low[ node ], low[ *it ]);
if (low[ *it ] >= found[ node ]) {
getBCC( edge(node, *it) );
}
} else {
low[ node ] = min(low[ node ], found[ *it ]);
}
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &N, &M);
while (M--) {
int x, y;
scanf("%d%d", &x, &y);
G[ x ].push_back ( y );
G[ y ].push_back( x );
}
for (int i = 1; i <= N; ++i) {
if (!T[ i ]) {
T[ i ] = i;
DFS( i );
}
}
printf("%d\n", bcc.size());
for (int i = 0; i < (int) bcc.size(); ++i) {
for (vector<int>::iterator it = bcc[ i ].begin(); it != bcc[ i ].end(); ++it) {
printf("%d ", *it);
}
printf("\n");
}
return 0;
}