Pagini recente » Cod sursa (job #846406) | Cod sursa (job #474672) | Cod sursa (job #2613627) | Cod sursa (job #1075788) | Cod sursa (job #2679801)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
using namespace std;
const int nmax = 100005;
vector<int> lis_vec[nmax];
vector<int> discover, low, art_vertex, parent, sol;
int timp, Root, rootChildren, nr_comp_biconexe;
struct muchie
{
int a, b;
};
muchie aux;
stack<muchie> st;
vector<int> componente[nmax];
ifstream fin("biconex.in");
ofstream fout("biconex.out");
void art_Point(int u)
{
int j, v;
++timp;
discover[u] = timp;//timpul descoperirii
low[u] = timp;//low_time initial
for(j = 0; j < lis_vec[u].size(); ++j)
{
v = lis_vec[u][j];// v e copilul lui u
if(!discover[v])
{
aux.a = u;
aux.b = v;
st.push(aux);//punem in stiva pana cand
parent[v] = u;//tatal lui v e u
if(u == Root)//1 // numaram cati fii are radacina(daca radacina are 1 sau 0 fii atunci este punct de articulatie)
++rootChildren;
art_Point(v);//apelare dfs
//dupa ce realizam parcurgerea pornim de la ultimul nod in care am ajuns
if(low[v] >= discover[u])//daca u este punct de articulatie
{
++nr_comp_biconexe;
do
{
componente[nr_comp_biconexe].push_back(st.top().b);//punem v-ul in componenta
aux = st.top();
st.pop();
}while(!(st.empty() || aux.a == u || aux.b == v));//cat timp nu s-a golit stiva sau am ajuns la unul dintre nodurile u si v
componente[nr_comp_biconexe].push_back(aux.a);
art_vertex[u] = 1;
}
if(low[u] > low[v]) //"mostenesc" low_time-ul CAND FAC INTOARCEREA
low[u] = low[v];
}
else if(v != parent[u])
{
if(low[u] > discover[v])
low[u] = discover[v];
}
}
}
int main()
{
int m, n, u, v, i;
fin>>n>>m;
for(i = 1; i <= m; ++i)
{
fin>>u>>v;
lis_vec[u].push_back(v);
lis_vec[v].push_back(u);
}
parent.assign(n+1, 0);
art_vertex.assign(n+1, 0);
low.assign(n+1, 0);
discover.assign(n+1, 0);
for(i = 1; i <= n; ++i)
{
if(!discover[i])
{
Root = i;
rootChildren = 0;
art_Point(i);
art_vertex[Root] = (rootChildren > 1);
}
}
fout<<nr_comp_biconexe<<'\n';
for(int i = 1;i <= nr_comp_biconexe;i++)
{
for(int j = 0;j < componente[i].size();j++)
fout<<componente[i][j]<<' ';
fout<<'\n';
}
return 0;
}//frunza nu e niciodata punct de articulatie