CAPCITY - Capital City - SPOJ Solution C++

Problem Link : CAPCITY

 

Hint : Topological Sort using DFS

 

C++ Solution :

 

#include<bits/stdc++.h>
using namespace std;
 
vector<int> adj[100001];
 
int cnt=0;
bool visited[100001]; 
void topo(int i,int n,vector<int> &s)
{
	visited[i]=1;
	for(auto it=adj[i].begin();it!=adj[i].end();it++)
	{
		if(!visited[*it])
			topo(*it,n,s);
	}
	s.push_back(i);
}
 
void dfs(int v,int n)
{
	visited[v]=1;
	cnt++;
	for(auto it=adj[v].begin();it!=adj[v].end();it++)
	{
		if(!visited[*it])
			dfs(*it,n);
	}
}
 
 
int main()
{
	int n,m,x,y;
	cnt=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		adj[i].clear();
	}
	memset(visited,0,sizeof(visited));
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		adj[x].push_back(y);
	}
	vector<int>s;
	topo(1,n,s);
	memset(visited,0,sizeof(visited));
	dfs(s[0],n);
	set<int>ans;
	for(int i=0;i<s.size();i++)
	{
		if(visited[s[i]])
			ans.insert(s[i]);
		else
			break;
	}
	cout<<cnt<<endl;
	for(int r: ans)
		cout<<r<<" ";
 
 
 
} 

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.