Pagini recente » Cod sursa (job #311465) | Cod sursa (job #1076601) | Cod sursa (job #1665695) | Cod sursa (job #1401312) | Cod sursa (job #2505025)
#include <iostream>
#include <bits/stdc++.h>
#define in_file "biconex.in"
#define out_file "biconex.out"
#define NMAX 100005
#define INF 1000003
using namespace std;
vector<int> G[NMAX];
vector<vector<int>> biconex_comp;
vector<bool> viz;
vector<int> lvl;
vector<int> min_achievable_lvl;
stack<pair<int, int>> edge;
void printVec(vector<int> v){
for(auto e : v){
fprintf(stdout, "%d, ", e);
}
}
void dfs(int node,int cameFrom){
viz[node]=true;
for(auto n:G[node]){
//if(n==cameFrom) continue;
if(!viz[n]){
edge.push({node, n});
min_achievable_lvl[n]=lvl[n]=lvl[node]+1;
dfs(n, node);
min_achievable_lvl[node]=min(min_achievable_lvl[n],min_achievable_lvl[node]);
if(min_achievable_lvl[n]>=lvl[node]){
vector<int> nodes;
while(edge.top().first != node){
nodes.push_back(edge.top().second);
edge.pop();
}
nodes.push_back(edge.top().second);
nodes.push_back(edge.top().first);
edge.pop();
biconex_comp.push_back(nodes);
}
}
else{
min_achievable_lvl[node]=min(min_achievable_lvl[node], lvl[n]);
}
}
}
int main()
{
freopen(in_file, "r", stdin);
freopen(out_file, "w", stdout);
int n,m;
cin>>n>>m;
int n1, n2;
while(m--){
cin>>n1>>n2;
G[n1].push_back(n2);
G[n2].push_back(n1);
}
viz=vector<bool>(n+1, false);
lvl=vector<int>(n+1);
min_achievable_lvl=vector<int>(n+1, INF);
min_achievable_lvl[0]=0;
lvl[0]=0;
for(int i=1; i<=n; i++){
if(!viz[i]){
dfs(i, 0);
}
}
cout<<biconex_comp.size()<<"\n";
for(auto comp:biconex_comp){
for(auto n: comp){
cout<<n<<" ";
}
cout<<"\n";
}
return 0;
}