Analiza programów

17.06.2009

Bombowanie

 
#include<vector>
#include<iostream>
using namespace std;
 
const int st = 1000000000; //REV: nazwa nieco tajemnicza
int wyn;
 
int n,m, licznik;
vector<int > numer, poprz, artic;
vector< vector<int> > graf;
 
//REV: wcięcia się coś posypały
//REV: za długi kod, ciężko ocenić poprawność, ale być może coś jest nie tak w przypadku grafu: 1->2, 1->2, 1->3, 1->3
int dfs(int u)
{
	int schow = u; //REV: mało klarowna nazwa
	numer[u] = licznik++;
	for (int i=0; i<graf[u].size(); i++)
	{
		int v = graf[u][i];
		if (v==u) continue; //REV: łatwy do uniknięcie continue, poza tym, czy takie krawędzie istnieją?
 
		if (v==poprz[u]) continue; //REV: łatwy do uniknięcie continue
 
		if (numer[v]==st)
		{
			poprz[v] = u;
			v = dfs(v);	
		}
		if (numer[schow] > numer[v]) schow=v;
	}
	if (schow==u && poprz[u]!=u) //REV: a co z korzeniem DFS, czy on nie powinien zawsze być punktem artykulacji?
    {                             
                                if(graf[u].size()>1 && artic[u+1]==0)//REV: nie łatwiej numerować od 0?
                                {
                                                      wyn++;
                                                     artic[u+1]=1;//REV: nie łatwiej numerować od 0?
 
 
 
                               }
                                if(graf[poprz[u]].size()>1 && artic[poprz[u]+1]==0)//REV: zduplikowana logika
                               {
                                                             wyn++;
                                                            artic[poprz[u]+1]=1;
 
 
                                }
 
    }
 
	return schow;
}
 
int main() 
{
    ios_base::sync_with_stdio(0);
	int a,b;
	cin>>n>>m;
	graf.clear(); graf.resize(n); //REV: czemu clear?, czy resize nie bierze dwóch argumentów?
	for (int i=0; i<m; i++)
	{
		cin>>a>>b;
		if (a==b) continue; //REV: łatwy do uniknięcia continue
		a--; b--; //REV: preincrementacja, to lepszy nawyk
		graf[a].push_back(b); 
		graf[b].push_back(a); //REV: duplikacja logiki
	} 
 
	numer.clear (); numer.resize (n,st); //REV: czemu clear?
	artic.resize(n+1,0); //REV: nie łatwiej numerować od 0?
	poprz.resize(n); //REV: czemu nie ma drugiego argumentu : 0?
	licznik = 1; //REV: dlaczego inicializacja jest tutaj?
 
 
	for (int u=0; u<n; u++)
		if (numer[u]==st) //REV: stałą lepiej po lewej
		{
			poprz[u] = u; dfs(u);
		}
		cout<<wyn<<endl;
		for(int i=1; i<=n; i++)//REV: nie łatwiej numerować od 0?
		if(artic[i]==1)
		cout<<i<<" ";
 
 
	return 0;
}
 

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com