Pagini recente » Cod sursa (job #1350637) | Cod sursa (job #615976) | Cod sursa (job #3153624) | Cod sursa (job #2362094) | Cod sursa (job #2175856)
#include<bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMAX = 100000;
stack<pair<int,int>> stk;
vector<int> G[NMAX+2];
int N, M, dfn[NMAX+2], low[NMAX+2];
vector<int> my_comp;
vector<vector<int>> bicon;
inline void normalize(vector<int>& vec)
{
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
}
void another_one(int x, int y)
{
my_comp.clear();
int lx, ly;
do {
auto pp = stk.top();
lx = pp.first;
ly = pp.second;
my_comp.push_back(lx);
my_comp.push_back(ly);
stk.pop();
}
while( !(lx == x && ly == y) );
bicon.push_back(my_comp);
}
bool viz[NMAX+2];
void print_stiva()
{
vector<pair<int,int>> vec;
while( !stk.empty() ) {
vec.push_back(stk.top());
stk.pop();
}
for( int i = vec.size() - 1; i >= 0; --i ) {
/// cerr << vec[i].first << ' ' << vec[i].second << '\n';
stk.push(vec[i]);
}
}
void dfs(int nod, int tata, int time)
{
///cerr << "stiva @ " << nod << '\n';
///print_stiva();
dfn[nod] = low[nod] = time;
viz[nod] = 1;
for( const auto& x : G[nod] ) {
if( x == tata ) continue;
if( viz[x] == 0 ) {
stk.push({nod, x});
dfs(x, nod, time + 1);
low[nod] = min(low[nod], low[x]);
if( low[x] >= dfn[nod] )
another_one(nod, x);
}
else {
low[nod] = min(low[nod], dfn[x]);
}
}
}
int main()
{
in >> N >> M;
for( int i = 1; i <= M; ++i ) {
int x,y;
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for( int i = 1; i <= N; ++i ) {
if( viz[i] ) continue;
dfs(i, -1, 1);
}
/// dfs2(2, -1);
out << bicon.size()<< '\n';
for( auto & ln : bicon ) {
normalize(ln);
for( const auto & x : ln ) out << x << ' ';
out << '\n';
}
return 0;
}