Pagini recente » Cod sursa (job #722190) | Cod sursa (job #1141202) | Cod sursa (job #790302) | Cod sursa (job #732730) | Cod sursa (job #2422233)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
int n,m;
std::vector<int> v[100500];
struct edge
{
int x,y;
};
bool vis[100500];
bool ins[100500];
int low[100500];
int disc[100500];
int root[100500];
std::stack<edge> s;
std::vector<int> rez[100500];
int rezc;
int countt;
void findSol(int x)
{
rezc++;
rez[rezc-1]=std::vector<int>();
rez[rezc-1].push_back(s.top().y);
// std::cout<<s.top().y<<" ";
while(!s.empty()&& s.top().x!=x)
{
rez[rezc-1].push_back(s.top().x);
// std::cout<<s.top().x<<" ";
s.pop();
}
if(!s.empty())
s.pop();
rez[rezc-1].push_back(x);
// std::cout<<x<<" ";
// std::cout<<"\n";
}
void specDFS(int u)
{
vis[u]=true;
low[u]=disc[u]=++countt;
// std::cout<<u<<"\n";
int children = 0;
for(int i=0;i<v[u].size();i++)
{
int elem = v[u][i];
if(!vis[elem])
{
children++;
root[elem]=u;
s.push({u,elem});
specDFS(elem);
low[u]=std::min(low[u],low[elem]);
if(children >1 && root[u]==0)
{
findSol(u);
findSol(u);
}
else if(root[u]!= 0 && low[elem]>= disc[u])
{
for(int k=0;k<children;k++)
findSol(u);
}
}
else if(elem!=root[u])
low[u]=std::min(low[u],disc[elem]);
}
// std::cout<<"end: "<<u<<"\n";
}
int main()
{
fin>>n>>m;
for(int i=0;i<m;i++)
{
int j,k;
fin>>j>>k;
v[j].push_back(k);
v[k].push_back(j);
}
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
specDFS(i);
}
if(!s.empty())
{
rezc++;
rez[rezc-1]=std::vector<int>();
rez[rezc-1].push_back(s.top().y);
while(!s.empty())
{
rez[rezc-1].push_back(s.top().x);
// std::cout<<s.top().x<<" ";
s.pop();
}
}
fout<<rezc<<"\n";
for(int i=0;i<rezc;i++)
{
for(int j=0;j<rez[i].size();j++)
fout<<rez[i][j]<<" ";
fout<<"\n";
}
}