Pagini recente » Cod sursa (job #831704) | Cod sursa (job #726304) | Cod sursa (job #1123131) | Cod sursa (job #2346301) | Cod sursa (job #2373976)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct IT
{
int x,y;
}temp;
stack<int>st;
int n,m,i,j,k;
vector<int>G[NMAX];
vector<int>dfs_discover,dfs_low,articulation_vertex,dfs_parent;
int ttime,dfsRoot,rootChildren;
vector< vector<int> > sol;
void Add(int tt, int fiu) {
vector<int> step;
while (st.top() != fiu) {
step.push_back(st.top());
st.pop();
}
step.push_back(fiu);
step.push_back(tt);
st.pop();
sol.push_back(step);
}
void articulationPoint(int u)
{
int v;
ttime++;
dfs_discover[u]=dfs_low[u]=ttime;
for(int j=0;j<G[u].size();j++)
{
v=G[u][j];
if(!dfs_discover[v])
{
dfs_parent[v]=u;
if(u==dfsRoot)rootChildren++;
temp.x=u;
temp.y=v;
st.push(v);
articulationPoint(v);
if(dfs_low[v]>=dfs_discover[u])
{
articulation_vertex[u]=1;
Add(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()
{
fin>>n>>m;
int u,v;
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);
articulation_vertex.assign(n+1,0);
dfs_discover.assign(n+1,0);
dfs_low.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;
}
}
fout<<sol.size()<<endl;
for (int i = 0; i <sol.size(); i++)
sort(sol[i].begin(),sol[i].end());
for (int i = 0; i <sol.size(); i++)
{
for(j=0;j<sol[i].size();j++)
fout<<sol[i][j]<<" ";
fout<<"\n";
}
return 0;
}