Pagini recente » Cod sursa (job #2682488) | Rating Bogdan Draghici (bimax145) | Cod sursa (job #3191068) | Cod sursa (job #2202972) | Cod sursa (job #1701067)
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1 + 1e5;
int depth[N];
vector<int> graph[N];
vector< vector<int> > C;
stack< pair<int, int> > stk;
void foundBCC(int X, int Y){
vector<int> v;
int x, y;
do {
x = stk.top().first;
y = stk.top().second;
stk.pop();
v.push_back(x);
v.push_back(y);
} while (x != X && y != Y);
sort( v.begin(), v.end() );
v.resize( unique(v.begin(), v.end()) - v.begin() );
C.push_back(v);
}
int dfs(int x, int T = -1, int D = 0){
int H = depth[x] = D;
for (int y : graph[x])
if ( depth[y] == -1 ){
stk.emplace(x, y);
int h = dfs(y, x, D + 1);
H = min(H, h);
if ( h >= D ) foundBCC(x, y);
} else if ( y != T )
H = min(H, depth[y]);
return H;
}
void biconex(int n){
memset( depth, -1, sizeof(depth) );
for (int i = 1; i <= n; i++)
if ( depth[i] == -1 )
dfs(i);
}
int main(){
ifstream in("biconex.in");
ofstream out("biconex.out");
int n, m, x, y;
in >> n >> m;
while (m--){
in >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
biconex(n);
out << C.size() << '\n';
for (vector<int>& v : C){
for (int x : v)
out << x << ' ';
out << '\n';
}
return 0;
}