Pagini recente » Cod sursa (job #2944092) | Cod sursa (job #2853054) | Cod sursa (job #442958) | Cod sursa (job #2030995) | Cod sursa (job #2576570)
#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 pda;}v[100003];///pda=punct de articulatie
int n,m;
bool tr[100003];
bool pda1=0;
stack <int> st;
struct componente{vector <int> c;}aux;
vector <componente> cmp;
//vector <int> vgol;
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)///e muchie din arbore adica e descendent direct
{
dfs(newnode,nod);
v[nod].dmin=min(v[nod].dmin,v[newnode].dmin);
if(v[nod].d<v[newnode].dmin);///e muchie critica
if(v[nod].d<=v[newnode].dmin)///totul din stack pana la newnode e o comp biconexa
{
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///e muchie de intoarcere
{
v[nod].dmin=min(v[nod].dmin,v[newnode].d);
}
if(v[nod].d<=v[newnode].dmin && nod!=1)v[nod].pda=1;
}
}
if(tata==1)///are fiu
{
if(pda1==0)pda1=1;
else v[1].pda=1;
}
}
int main()
{
f>>n>>m;
for(int 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;v[1].dmin=1;
dfs(1,0);
g<<cmp.size()<<'\n';;
for(int i=0;i<cmp.size();i++){
for(int j=0;j<cmp[i].c.size();j++)
g<<cmp[i].c[j]<<" ";g<<'\n';}
}