Pagini recente » Cod sursa (job #1602770) | Cod sursa (job #1518718) | Cod sursa (job #1518805) | Cod sursa (job #655536) | Cod sursa (job #2820882)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
std::ifstream in("biconex.in");
std::ofstream out("biconex.out");
const int N=100000;
const int M=200000;
struct edge
{
int from;
int to;
};
std::vector<int> v[N+1];
std::vector<std::vector<int>> ans;
edge muchii[M+1];
std::stack<int> q;
int timp=0;
int t[N+1];
int low[N+1];
int parent[N+1];
int children[N+1];
void Dfs(int i)
{
t[i]=low[i]=++timp;
for(int edg : v[i])
{
int copil=muchii[edg].from+muchii[edg].to-i;
if(!t[copil])
{
//std::cout<<i<<" "<<copil<<"\n";
q.push(edg);
children[i]++;
parent[copil]=i;
Dfs(copil);
low[i]=std::min(low[i], low[copil]);
if(parent[i]==0 && children[i]>1)
{
std::vector<int> prov;
while(q.top()!=edg)
{
prov.push_back(q.top());
q.pop();
}
prov.push_back(q.top());
q.pop();
ans.push_back(prov);
}
if(parent[i]!=0 && low[copil]>=t[i])
{
std::vector<int> prov;
while(q.top()!=edg)
{
prov.push_back(q.top());
q.pop();
}
prov.push_back(q.top());
q.pop();
ans.push_back(prov);
}
}
else if(parent[i]!=copil)
{
low[i]=std::min(low[i], t[copil]);
}
}
}
int main()
{
int n, m, x, y;
in>>n>>m;
for(int i=1; i<=m; i++)
{
in>>x>>y;
muchii[i].from=x;
muchii[i].to=y;
v[x].push_back(i);
v[y].push_back(i);
}
Dfs(1);
std::vector<int> prov;
while(!q.empty())
{
prov.push_back(q.top());
q.pop();
}
ans.push_back(prov);
out<<ans.size()<<"\n";
for(auto cnt : ans)
{
for(int i : cnt)
{
out<<muchii[i].from<<" ";
}
out<<muchii[*cnt.begin()].to<<"\n";
}
}