Pagini recente » Cod sursa (job #131273) | Cod sursa (job #904097) | Cod sursa (job #2912420) | Cod sursa (job #1727058) | Cod sursa (job #3228547)
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
using namespace std;
vector<vector<int>> gr;
vector<int> tim, fun;
vector<bool> used;
stack<int> C;
stack<pair<int,int>> st;
vector<set<int>> point;
int times = 0;
void vert(int u,int v){
set<int> key;
int bu,bv;
do{
bu=st.top().first;
bv=st.top().second;
st.pop();
key.insert(bu);
key.insert(bv);
}while(bu != u || bv !=v );
point.push_back(key);
}
void dfs(int v,int p=-1){
used[v]=1;
tim[v]=times++;
fun[v]=tim[v];
int child=0;
for (auto u:gr[v])
{
if(u==p){
continue;
}
if(fun[u]== -1){
st.push({v,u});
dfs(u,v);
fun[v]=min(fun[u],fun[v]);
if(fun[u]>=tim[v])
vert(v,u);
}
else{
fun[v]=min(fun[v],tim[u]);
}
}
}
int main() {
int n, m;
cin >> n >> m;
gr=vector<vector<int>>(n);
tim=vector<int>(n);
fun=vector<int>(n,-1);
used= vector<bool>(n,0);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
gr[u].push_back(v);
gr[v].push_back(u);
}
dfs(0);
cout<<point.size()<<"\n";
for (auto i:point)
{
for (auto j:i)
{
cout<<j+1<<" ";
}
cout<<"\n";
}
return 0;
}