1 / 2
Feb 2021

I am trying to solve the problem capacity - capital city. I got runtime error(sigabrt). Can anyone please tell me where I went wrong?

Here is my code:

using namespace std;
#include<bits/stdc++.h>

int num_v,num_e;
vectoradj[200001];
vectortranspose[200001];
stacks;

int flag = 0;
int node;
int scc[200001];

vectorvertex;

void init(){

for (int i = 0; i <= num_v; ++i)
{
    adj[i].clear();
    transpose[i].clear();
 
}
while(s.size())s.pop();
vertex.clear();

}

void dfs_transpose(int u, bool visited[]){
visited[u]=true;
scc[u] = node;
// cout<<node<<" ";

for (int i = 0; i < transpose[u].size(); ++i)
{   
    int v = transpose[u][i];
    if(visited[v]==false)
        dfs_transpose(v,visited);
}

}

void dfs(int u, bool visited[]){
visited[u]=true;
for (int i = 0; i < adj[u].size(); ++i)
{
int v = adj[u][i];
if(!visited[v])
dfs(v,visited);
}
s.push(u);
}

void printSCC(){

bool visited[num_v+1];
for (int i = 1; i <= num_v; ++i)
    visited[i]=false;


for (int i = 1; i <= num_v; ++i)
{
    if(visited[i]==false)
        dfs(i,visited);
}


for (int i = 1; i <= num_v; ++i)
    visited[i]=false;


node = 0;

while (s.empty() == false) 
{ 
    int v = s.top(); 
    s.pop(); 
  
    
    if (!visited[v]) 
    { 
        node++;
        dfs_transpose(v, visited);
    } 
     
}
// cout<<node<<endl;

}
int main()
{
int U, V, W, a, b, N, M;
init();

cin >> num_v;   //number of nodes
cin >> num_e;   //number of edges
M = num_e;
while(M--)
{
    cin >> U >> V;
    if(find(adj[U].begin(),adj[U].end(),V)!=adj[U].end()) continue;
    adj[U].push_back(V);
    transpose[V].push_back(U);
}
printSCC();


int outdegree[node+5];
for (int i = 0; i <= num_v; ++i)
{
    outdegree[i]=0;
}


for (int i = 1; i <=num_v; ++i)
{
    for (int j = 0; j < adj[i].size(); ++j)
    {
        int u = i;
        int v = adj[i][j];
        if(scc[u]!=scc[v]) {
                  
            outdegree[scc[u]]++;
        }
    }
}
int cnt = 0;


for (int i = 1; i <= node; ++i)
{
    if(outdegree[i]==0)
    {
        cnt++;
    }
}

if (cnt!=1) cout<<"0"<<endl;

else
{
    for (int i = 1; i <=num_v ; ++i)
    {
        if(outdegree[scc[i]]==0) 
        {
            vertex.push_back(i);
        }
    }

    cout<<vertex.size()<<endl;
    for (int i = 0; i < vertex.size(); ++i)
    {
        cout<<vertex[i];
        if(i!=vertex.size()-1) cout<<" ";
    }
    puts("");
}
return 0;

}

  • created

    Feb '21
  • last reply

    Feb '21
  • 1

    reply

  • 707

    views

  • 2

    users

Your code has been mangled by the smart editor. To stop this happening, either indent the whole code by four spaces, or put three backticks ``` on a line by themselves both before and after the code.