Cod sursa(job #561075)

Utilizator avram_florinavram florin constantin avram_florin Data 18 martie 2011 20:46:19
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#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;
}