Pagini recente » Cod sursa (job #2565293) | Cod sursa (job #1876747) | Cod sursa (job #1007136) | Cod sursa (job #1391431) | Cod sursa (job #1586745)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define pb push_back
#define MaxN 100001
int n, m;
vector<int> L(MaxN), niv(MaxN);
vector<bool> viz(MaxN);
vector<int> G[MaxN];
stack<pair<int,int> >_stack;
vector<vector<int> >components;
void Read();
void Df(int, int);
void GetComponent(int, int);
void Write();
int main() {
Read();
Df(1,0);
Write();
fin.close();
fout.close();
return 0;
}
void Write() {
fout << components.size() << '\n';
for ( auto comp : components ) {
sort(comp.begin(), comp.end() );
comp.erase(unique(comp.begin(), comp.end()), comp.end() );
for ( const auto c : comp )
fout << c << ' ';
fout << '\n';
}
}
void Df(int nod, int father) {
L[nod] = niv[nod] = niv[father] + 1;
viz[nod] = true;
for ( const int x : G[nod] ) {
if ( x == father)
continue;
if ( !viz[x] ) {
_stack.push({x,nod}); // fiul si tatal <3
Df(x, nod);
L[nod] = min(L[nod], L[x]);
if ( L[x] >= niv[nod] )
GetComponent(x, nod);
}
else // back edge sanchi
L[nod] = min(L[nod], niv[x]);
}
}
void GetComponent(int x, int father) {
vector<int> c;
int y, y_father;
do {
y = _stack.top().first;
y_father = _stack.top().second;
_stack.pop();
c.pb(y);
c.pb(y_father);
}while( y != x && y_father != father && !_stack.empty() );
components.pb(c);
}
void Read() {
fin >> n >> m;
int x, y;
while(m--) {
fin >> x >> y;
G[x].pb(y);
G[y].pb(x);
}
}