Pagini recente » Cod sursa (job #341997) | Cod sursa (job #342729) | Cod sursa (job #1491725) | Cod sursa (job #1498293) | Cod sursa (job #2796400)
#include <bits/stdc++.h>
#define DIM_MAX 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<bool> v(DIM_MAX);
vector<int> v1(DIM_MAX), v2(DIM_MAX), v3(DIM_MAX);
vector<vector<int>> mat(DIM_MAX);
vector<vector<int> > comp;
deque<pair<int, int> > stiv;
void adaug_comp(int x, int y) {
int a, b;
vector<int> row;
vector<bool> added(DIM_MAX);
while(!stiv.empty() && (a!=x || b!=y)) // trecem prin striva si adaugam e un nou row elementele comp biconexe
{
a = stiv.back().first;
b = stiv.back().second;
stiv.pop_back();
if(!added[a]){
row.push_back(a);
added[a]=true;}
if(!added[b])
{row.push_back(b);
added[b]=true;}
}
sort(row.begin(), row.end());
comp.push_back(row);
}
void dfs(int x) {
v[x] = true;
v2[x] = v1[x] = v2[v3[x]]+1;
for(auto a: mat[x]) { // trecem prin elementele adiacente nodului
if(!v[a]) { // daca nu e vizitat
stiv.push_back({x, a});
v3[a] = x;
dfs(a);
if(v1[a] >= v2[x])
adaug_comp(x, a);
v1[x] = min(v1[x], v1[a]);
} else if(a != v3[x]) // daca nodul adiacent lui x nu este nodul precendent din care vine x
v1[x] = min(v1[x], v2[a]);
}
}
int main() {
int n,m;
f >> n >> m;
for(int i = 0 ; i < m ; ++i){
int a, b;
f >> a >> b;
mat[a].push_back(b);
mat[b].push_back(a);
}
dfs(1);
g << comp.size() << '\n';
for(auto a: comp) {
for(auto b:a)
g << b << ' ';
g << '\n';
}
}