Pagini recente » Cod sursa (job #1842878) | Cod sursa (job #242365) | Cod sursa (job #1895692) | Cod sursa (job #495762) | Cod sursa (job #2404639)
#include <bits/stdc++.h>
#define MAXIM 100005
using namespace std;
ifstream f ("biconex.in") ;
ofstream g ("biconex.out") ;
int N , M , nr = 0 , nr2 = 0;
int low[MAXIM] , niv[MAXIM] , t[MAXIM] , sol[MAXIM];
vector <int> v[MAXIM] ;
vector <pair <int ,int> > st;
void dfs (int k)
{
int i , x ;
low[k] = niv[k] ;
int sz = v[k].size() ;
for (int i = 1 ; i < sz ; ++i)
{
x = v[k][i]; // vecin ;
if (!niv[x]) // e nevizitat
{
niv[x] = niv[k] + 1 ;
t[x] = k ; // k e tatal lui 'x';
dfs(x) ;
low[k] = min(low[k] , low[x]) ;
if (low[x] >= niv[k]) nr ++; // k este pct de articulatie
}
else if (x != t[k]) low[k] = min(low[k],niv[x]) ;
}
}
void reinitializare()
{
for (int i = 1 ; i <= N ; ++i)
niv[i] = t[i] = low[i] = 0;
return;
}
void dfs2(int k)
{
int x , a1,a2;
int var;
low[k] = niv[k] ;
int sz = v[k].size() ;
for (int i = 0 ; i < sz ; ++i)
{
x = v[k][i];
if (!niv[x])
{
niv[x] = niv[k] + 1;
t[x] = k;
dfs2(x) ;
low[k] = min(low[x],low[k]) ;
if (low[x] >= niv[k])
{
nr2 = 0 ;
do
{
var = st.size()-1;
a1 = st[var].first;
a2 = st[var].second;
sol[++nr2] = a1;
sol[++nr2] = a2;
st.pop_back() ;
} while (!st.empty() && !((a1==x && a2==k) || (a1==k && a2==x)));
}
sort(sol+1,sol+nr2+1) ;
for (int j = 1 ; j <= nr2 ; ++j)
if (sol[j] != sol[j-1]) g << sol[j] << ' ' ;
g << '\n';
}
else if (x != t[k]) low[k] = min (low[k] , niv[x]) ;
}
}
int main()
{
int x, y;
f >> N >> M ;
for (int i = 1 ; i <= M ; ++i)
{
f >> x >> y;
v[x].push_back(y) ;
v[y].push_back(x) ;
}
niv[1] = 1 ;
dfs(1); // ptr aflare componente biconexe
g << nr << '\n';
reinitializare();
niv[1] = 1;
dfs2(1) ;
return 0;
}