Блог пользователя madhav_thakker

Exit code is -1073741819 (RunTime Error) (RESOLVED)
Автор madhav_thakker, история, 7 лет назад, По-английски

solution

const int maxN = 5013;

std::vector< vector<int> > graph(maxN);
std::vector<bool> visited(maxN);
set<pii> bad_vertices;

void dfs(int u, int par){
	visited[u] = true;
	tr(bad_vertices, it){
		if(it->second == u){
			bad_vertices.erase(make_pair(graph[u].size(), u));
		}
	}
	for(int v:graph[u]){
		if(v==u){
			continue;
		}
		if(!visited[v]){
			// trace(v, u);
			dfs(v, u);
		}
	}
}

signed main(){
	fastio;
	int n, m, s;
	cin>>n>>m>>s;
	int x, y;
	int ans = 0;
	for (int i = 0; i < m; ++i){
		cin>>x>>y;
		graph[x].push_back(y);
	}
	for (int i = 1; i <= n; ++i){
		visited[i] = false;
		bad_vertices.insert(make_pair(graph[i].size(), i));
	}
	dfs(s, -1);
	while(bad_vertices.size()>0){
		ans++;
		dfs((bad_vertices.rbegin())->second, -1);
	}
	cout<<ans<<endl;
}

Can anyone help me with the RunTime Error. It runs alright on my local machine. Thanks

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 5   Проголосовать: нравится +13 Проголосовать: не нравится

On my local machine using C++14, your code returns the same Segmentation Fault. The compiled code cannot increment the it pointer properly at run-time inside the dfs() function after erasing the present item whose address is stored in it.

Try to replace the loop:

tr(bad_vertices, it){
    if(it->second == u){
        bad_vertices.erase(make_pair(graph[u].size(), u));
    }
}

with the following code:

vector< set<pii>::iterator > deleted;

tr(bad_vertices, it)
   if( it->second == u )
        deleted.push_back( it );

while( !deleted.empty() )
    bad_vertices.erase( deleted.back() ), deleted.pop_back();

This should fix the problem.

UPDATE

Since the pair object make_pair( graph[u].size(), u ) can appear at most once in the ordered set bad_vertices, the following binary search method for erasing it from the set is a more efficient approach than the linear search loop.

auto it = bad_vertices.find( make_pair(graph[u].size(), u ) );

if ( it != bad_vertices.end() ) 
    bad_vertices.erase( it );
→ Ответить