Pagini recente » Cod sursa (job #2224763) | Cod sursa (job #2453837) | Cod sursa (job #2788783) | Cod sursa (job #2363918) | Cod sursa (job #2394067)
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> g[100005];
vector <int> dfs_discover,dfs_low,articulation_vertex,dfs_parent;
vector<int> sol[100005];
stack< pair<int, int> >st;
int cc;
int time,dfsroot,rootchildren,n;
void golire(int u, int v)
{
int i, j;
sol[cc].push_back(st.top().second);
do
{
i = st.top().first;
j = st.top().second;
sol[cc].push_back(i);
//fout<<i<<" "<<j<<'\n';
st.pop();
}while(i!=u && j!=v);
//fout<<'\n';
}
void articulationpoint(int u)
{
int v,j;
time++;
dfs_discover[u]=time;
dfs_low[u]=time;
for(j=0;j<g[u].size();j++)
{
v=g[u][j];
if(!dfs_discover[v])
{
st.push({u, v});
dfs_parent[v]=u;
if(u==dfsroot)
rootchildren++;
articulationpoint(v);
if(dfs_low[v]>=dfs_discover[u])
{
articulation_vertex[u]=1;
cc++;
golire(u, v);
}
dfs_low[u]=min(dfs_low[u],dfs_low[v]);
}
else
if(dfs_parent[u]!=v)
dfs_low[u]=min(dfs_low[u],dfs_discover[v]);
}
}
int main()
{
int m,u,v,i;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs_parent.assign(n+1,0);
dfs_low.assign(n+1,0);
dfs_discover.assign(n+1,0);
articulation_vertex.assign(n+1,0);
for(i=1;i<=n;i++)
if(dfs_discover[i]==0)
{
dfsroot=i;
rootchildren=0;
articulationpoint(i);
articulation_vertex[dfsroot]=rootchildren>1;
}
//for(i=1;i<=n;i++)
//if(articulation_vertex[i]==1)
//out<<i<<"\n";
fout<<cc<<'\n';
for(int i=1; i<=cc; i++)
{
for(int j= 0; j<sol[i].size(); j++)
fout<<sol[i][j]<<" ";
fout<<'\n';
}
return 0;
}