Cod sursa(job #712263)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 13 martie 2012 11:11:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
# include <fstream>
# include <vector>
# define dim 200001
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,nr,u,st1[dim],st2[dim],c[dim],lv[dim] ;
bool viz[dim] ;
vector <int> v[dim];
vector <int> sol[dim];

void add(int k,int x)
{int xx , yy ;
    nr++;
    while (xx != k || yy != x)
    {  xx = st1[u];
       yy = st2[u];
       sol[nr].push_back(yy);
	   u--;
    }
    sol[nr].push_back(xx);
}
void dfs(int k,int par)
{int x, i;
    lv[k] = lv[par] + 1 ;
    c[k] = lv[k];
    viz[k] = 1;
    for (i=0;i<v[k].size();++i)
    {   x = v[k][i];
	    if (!viz[x])
	    {   u++;
		    st1[u] = k;
		    st2[u] = x;
		    dfs(x,k);
		    if (c[x] < c[k] )
			    c[k] = c[x];
		    if (c[x]>=lv[k])
			    add(k,x);
        }
	    else 
		    if (x!=par && c[x]<c[k])
			    c[k] = c[x];
    }
}
int main()
{int a,b,i,j;
    fin >> n >> m;
	for (i=1;i<=m;++i)
	{   fin >> a >> b;
		v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,0);
    fout << nr << "\n";
    for( int i = 1 ; i <= nr ; ++i )
    {   for (j=0;j<sol[i].size();++j)
			fout << sol[i][j] << " ";
	    fout << "\n";
    }
	return 0;
}