Pagini recente » Cod sursa (job #579772) | Cod sursa (job #923248) | Cod sursa (job #2915710) | Cod sursa (job #2598878) | Cod sursa (job #2394075)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector <int> g[100001];
vector <int> dfs_discover,dfs_low,articulation_vertex,dfs_parent;
stack < pair<int,int> > st;
vector <int> graf[100001];
int tim,dfsroot,rootchildren,n,numar=1;
void golire(int u,int v)
{
int i=0,j=0;
graf[numar].push_back(st.top().second);
do
{
i=st.top().first;
j=st.top().second;
graf[numar].push_back(i);
st.pop();
}while(i!=u && j!=v);
numar++;
}
void articulationpoint(int u)
{
int v,j;
tim++;
dfs_discover[u]=tim;
dfs_low[u]=tim;
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;
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,j;
in>>n>>m;
for(i=1;i<=m;i++)
{
in>>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;
}
numar--;
out<<numar<<"\n";
for(i=1;i<=numar;i++)
{
for(j=0;j<graf[i].size();j++)
out<<graf[i][j]<<" ";
out<<"\n";
}
return 0;
}