Pagini recente » Cod sursa (job #75711) | Cod sursa (job #2554526) | Cod sursa (job #902635) | Cod sursa (job #195033) | Cod sursa (job #2576702)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct noduri{vector <int> v;int d;int dmin;bool nint;}v[100003];///nint=nod de intersectie pt biconexe
int n,m,i;
bool tr[100003];
bool nint1=0;
stack <int> st;
struct componente{vector <int> c;}aux;
vector <componente> cmp;
void DFS(int nod,int tata)
{
st.push(nod);
tr[nod]=1;
v[nod].d=v[tata].d+1;
v[nod].dmin=v[nod].d;
for(int i=0;i<v[nod].v.size();i++)
{
int newnode=v[nod].v[i];
if(newnode!=tata)
{
if(tr[newnode]==0)///muchia face parte din arbore
{
DFS(newnode,nod);
v[nod].dmin=min(v[nod].dmin,v[newnode].dmin);
if(v[newnode].dmin>=v[nod].d)
{
cmp.push_back(aux);
while(st.top()!=newnode)
{
cmp[cmp.size()-1].c.push_back(st.top());
st.pop();
}
cmp[cmp.size()-1].c.push_back(st.top());
st.pop();
cmp[cmp.size()-1].c.push_back(nod);
}
}
else///muchie secundara
{
v[nod].dmin=min(v[nod].dmin,v[newnode].d);
}
if(nod!=1 && v[newnode].dmin>=v[nod].d)v[nod].nint=1;
}
}
if(tata==1)
{
if(nint1==0)nint1=1;
else v[1].nint=1;
}
}
int main()
{
f>>n>>m;
for(i=1;i<=m;i++)
{
int x,y;
f>>x>>y;
v[x].v.push_back(y);
v[y].v.push_back(x);
}
v[1].d=1;
DFS(1,0);
g<<cmp.size()<<'\n';
for(i=0;i<cmp.size();i++)
{
for(int j=0;j<cmp[i].c.size();j++)
g<<cmp[i].c[j]<<" ";
g<<'\n';
}
}