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
last reply
- 1
reply
- 707
views
- 2
users