Pagini recente » Cod sursa (job #821393) | Cod sursa (job #1203306) | Cod sursa (job #2707169) | Cod sursa (job #1117661) | Cod sursa (job #2701089)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
bool viz[100005];
vector<int> nodes[100005];
vector <vector <int> > rez;
stack <pair <int, int > > edges;
int n, m, depth[100005], lowlink[100005],index = 1;
void solve(pair<int, int > edge)
{
vector <int> vec;
int k = 0;
int ok = 1;
while(ok)
{
pair < int , int > vf = edges.top();
edges.pop();
vec.push_back(vf.first);
vec.push_back(vf.second);
if(vf == edge)
break;
}
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
rez.push_back(vec);
vec.clear();
}
void dfs(int node, int parent){
depth[node] = depth[parent] + 1;
lowlink[node] = depth[node];
viz[node] = true;
for(auto &it:nodes[node]){
if(it == parent)
continue;
if(!viz[it])
{
edges.push({node, it});
dfs(it, node);
lowlink[node] = min(lowlink[it], lowlink[node]);
if(lowlink[it] >= depth[node])
solve({node,it});
}
else
lowlink[node] = min(lowlink[node], depth[it]);
}
}
int main()
{
fin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
nodes[x].push_back(y);
nodes[y].push_back(x);
}
dfs(1,0);
fout << rez.size() << "\n";
for( auto &it : rez)
{
for(auto &v: it)
fout << v << " ";
fout << "\n";
}
return 0;
}