Pagini recente » Cod sursa (job #2441986) | Cod sursa (job #113188) | Cod sursa (job #886693) | Cod sursa (job #3180159) | Cod sursa (job #3030220)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
using pi = pair<int,int>;
int n,m,a,b;
vector<vector<int>> G;
vector<int> lvl,low;
stack<pi> stk;
vector<vector<int>> cbc;
vector<int> c;
void extract(int x,int y)
{
c.clear();
while(true)
{
int tx = stk.top().first,ty = stk.top().second;
stk.pop();
c.push_back(tx),c.push_back(ty);
if(tx == x && ty == y)break;
}
sort(c.begin(),c.end());
c.erase(unique(c.begin(),c.end()),c.end());
cbc.push_back(c);
}
void Dfs(int x,int p)
{
lvl[x] = low[x] = lvl[p] + 1;
for(auto i : G[x])
if(lvl[i] == 0)
{
stk.push({i,x});
Dfs(i,x);
low[x] = min(low[x],low[i]);
if(low[i] >= lvl[x])
extract(i,x);
}
else
low[x] = min(low[x],lvl[i]);
}
int main()
{
cin>>n>>m;
G = vector<vector<int>>(n+1);
lvl = low = vector<int>(n+1);
while(m--)
{
cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
Dfs(1,0);
cout<<cbc.size()<<'\n';
for(auto i : cbc)
{
for(auto j : i)
cout<<j<<' ';
cout<<'\n';
}
return 0;
}