Pagini recente » Cod sursa (job #1739112) | Cod sursa (job #1537094) | Monitorul de evaluare | Cod sursa (job #1043521) | Cod sursa (job #2503821)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int nmax=100005;
vector<int> G[nmax];
stack<pair<int,int>>Q;
vector<vector<int> >sol;
int low[nmax],dt[nmax],fath[nmax];
bool viz[nmax];
int n,m,a,b;
void comp(int node,int x)
{
vector<int>q;
int fx,fy;
fx=Q.top().first;
fy=Q.top().second;
Q.pop();
q.push_back(fx);q.push_back(fy);
while(fx!=node || fy!=x)
{
fx=Q.top().first;
fy=Q.top().second;
Q.pop();
q.push_back(fx);q.push_back(fy);
}
sol.push_back(q);
}
void DFS(int node,int t)
{
viz[node]=1;
dt[node]=low[node]=t;
for(auto x: G[node])
{
if(!viz[x])
{
fath[x]=node;
Q.push({node,x});
DFS(x,t+1);
low[node]=min(low[node],low[x]);
if(low[x]>=dt[node])
{
comp(node,x);
}
}
else if(x!=fath[node])
{
low[node]=min(low[node],dt[x]);
}
}
}
int main()
{
f>>n>>m;
for(int i=1;i<=m;i++)
{
f>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
DFS(1,0);
g<<sol.size()<<"\n";
for(int i=0;i<sol.size();i++)
{
sort(sol[i].begin(),sol[i].end());
sol[i].erase(unique(sol[i].begin(),sol[i].end()),sol[i].end());
for(auto x:sol[i])
g<<x<<" ";
g<<"\n";
}
return 0;
}