Pagini recente » Cod sursa (job #87560) | Cod sursa (job #2657417) | Cod sursa (job #252927) | Cod sursa (job #1629050) | Cod sursa (job #561075)
Cod sursa(job #561075)
#include<fstream>
#include<cstdio>
#define MaxN 1001
using namespace std;
ifstream f ("f.in");
ofstream g ("g.out");
int n,m,nr,start,vfs,nrfii,art[MaxN],lvl[MaxN],low[MaxN],a[MaxN][MaxN];
struct muchie{
int son,father;
};
muchie st[MaxN];
int minim(int x,int y)
{
if( x < y )
return x;
return y;
}
void afisare(int x,int y)
{
muchie p;
do
{
p = st[vfs];
g << p.father << ' ' << p.son << '\n';
vfs--;
}
while( p.father != x || p.son != y);
g << '\n';
}
void dfs(int nod,int father)
{
int i,aux;
nr++;
lvl[nod] = low[nod] = nr;
for( i = 1 ; i <= a[nod][0] ; i++ )
{
aux = a[nod][i];
if( aux != father && lvl[aux] < lvl[nod] )
{
st[++vfs].father = nod;
st[vfs].son = aux;
}
if( lvl[aux] == -1 )
{
if( nod == start )
nrfii++;
dfs(aux,nod);
low[nod] = minim(low[nod],low[aux]);
if( low[aux] >= lvl[nod] )
{
if( nod != start )
art[nod] = 1;
afisare(nod,aux);
}
}
else
if( aux != father )
low[nod] = minim(low[nod],lvl[aux]);
}
}
int main(void)
{
f >> n >> m;
int i,x,y;
for( i = 1 ; i <= m ; i++ )
{
f >> x >> y;
a[x][++a[x][0]] = y;
a[y][++a[y][0]] = x;
}
for( i = 0; i <= n ; i++ )
lvl[i] = low[i] = -1;
start = 1;
dfs(start,-1);
if( nrfii > 1 )
art[start] = 1;
for( i = 1 ; i <= n ; i++ )
if( art[i] )
g << i << ' ';
g << '\n';
f.close();
g.close();
return 0;
}