Pagini recente » Cod sursa (job #2923853) | Cod sursa (job #2565495) | Cod sursa (job #3224456) | Cod sursa (job #1267742) | Cod sursa (job #1391123)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
const int dim = 100005;
ifstream f("biconex.in");
ofstream g("biconex.out");
pair<int,int> muchie;
vector < pair<int, int> > muchii;
vector <int> vf[dim];
stack < vector<int> > comp_bicon;
int viz[dim], nv[dim], L[dim], t[dim], crit[dim];
int n, m, nr, rad;
//int bicon;
void citeste_graf()
{
int a,b;
f>>n>>m;
for(int i = 0; i < m; i++)
{
f>>a>>b;
vf[a].push_back(b);
vf[b].push_back(a);
}
}
void DF(int nod)
{
int nod2;
viz[nod] = 1;
L[nod] = nv[nod];
int nr_noduri = vf[nod].size();
for(int i = 0; i < nr_noduri; i++)
{
nod2 = vf[nod][i];
if(!viz[nod2])
{
muchie = make_pair(nod, nod2);
muchii.push_back(muchie);
nv[nod2] = nv[nod] +1;
t[nod2]=nod;
if(nod == rad)
nr++;
DF(nod2);
if(L[nod] > L[nod2])
L[nod] = L[nod2];
if(L[nod2] >= nv[nod])
{
crit[nod] = 1;
vector <int> v;
do
{
muchie = muchii.back();
v.push_back(muchie.first), v.push_back(muchie.second);
muchii.pop_back();
}while(muchie.first != nod && muchie.second != nod2);
comp_bicon.push(v);
}
}
else
if(nod2 != t[nod] && L[nod] > nv[nod2])
L[nod] = nv[nod2];
}
}
int main()
{
citeste_graf();
for(int i = 1; i <= n; i++)
if(!viz[i])
{
nv[i] = 1;
rad = i;
nr = 0;
DF(i);
crit[rad] = nr >1;
}
g<<comp_bicon.size()<<'\n';
while(!comp_bicon.empty())
{
vector<int> v;
int el;
v = comp_bicon.top();
comp_bicon.pop();
sort(v.begin(), v.end());
el = v[0];
g<<el<<' ';
for(int i = 1; i < v.size(); i++)
if(v[i]!=el)
{
g<<v[i]<<' ';
el = v[i];
}
g<<'\n';
}
return 0;
}