Pagini recente » Cod sursa (job #2182336) | Cod sursa (job #1563281) | Cod sursa (job #752168) | Cod sursa (job #1483372) | Cod sursa (job #2508081)
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <bitset>
using namespace std;
//#include <iostream>
#include <fstream>
//ifstream cin ("input.in");
//ofstream cout ("output.out");
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
static const int NMAX = 1e5+5;
int depth[NMAX];
int minDepth[NMAX];
stack <int> s;
vector <int> graph[NMAX];
vector <int> biconnectedComp[NMAX];
int k;
void dfs (int vertex, int father) {
depth[vertex] = depth[father]+1;
minDepth[vertex] = depth[vertex];
s.push(vertex);
for ( auto x:graph[vertex] ) {
if ( depth[x] ) {
//Daca din vertex dau de un nod deja vizitat, imi recalculez minDepth pt vertex
if ( x != father ) {
minDepth[vertex] = min(depth[x], minDepth[vertex]);
}
}
else {
dfs(x, vertex);
//Verific daca, facand dfs in continuare, pot ajunge la un nod aflat mai sus in arbore
minDepth[vertex] = min(minDepth[vertex], minDepth[x]);
//Verific daca cel mai de sus nod in care as putea ajunge din fiu folosind alte muchii se afla sub tata
//Daca da, inseamna ca tatal (vertex) este punct de articulatie
//=> Toate nodurile din stiva (pana in vertex) apartin aceleiasi componente biconexe
if ( minDepth[x] >= depth[vertex] ) {
cout<<"mindepth de "<<x<<" "<<minDepth[x]<<" "<<"depth de "<<vertex<<" "<<depth[vertex]<<'\n';
++k;
while ( s.top() != x ) {
biconnectedComp[k].push_back(s.top());
s.pop();
}
biconnectedComp[k].push_back(x);
biconnectedComp[k].push_back(vertex);
s.pop();
//^Imi scot x-ul
//^De observat ca vertex inca poate sa apartina altei componente biconexe
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin>>n>>m;
for ( int i = 1; i <= m; ++i ) {
int a, b;
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(1, 0);
cout<<k<<'\n';
for ( int i = 1; i <= k; ++i ) {
for ( auto x:biconnectedComp[i] ) {
cout<<x<<" ";
}
cout<<'\n';
}
}