fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int ans=0;
  4. queue<int> q;
  5. int bfs(vector<int> v[],int vis[],int c)
  6. {
  7.    while(!q.empty())
  8.    {
  9.    	 int x=q.front();
  10.    	 q.pop();
  11.    	 for(int i=0;i<v[x].size();i++)
  12.    	 {    
  13.    	 	int zz=v[x][i];
  14.    	 	if(vis[zz]==1)
  15.    	 		continue;
  16.    	 	vis[zz]=1;
  17.    	 	q.push(zz);
  18.    	 }
  19.    }
  20.    int max=0;
  21.    for(int i=1;i<c+1;i++)
  22.    {
  23.    	 if(vis[c]==0)
  24.    	 {
  25.    	 	if(max>v[c].size())
  26.    	 		max=c;
  27.    	 }
  28.    }
  29.    return max;
  30. }
  31. int main()
  32. {
  33. 	int c,m,s;
  34. 	cin>>c>>m>>s;
  35. 	vector<int>v[c+1];
  36. 	for(int i=0;i<m;i++)
  37. 	{
  38. 		int x,y;
  39. 		cin>>x>>y;
  40. 		v[x].push_back(y);
  41. 	}
  42. 	int vis[c+1];
  43. 	for(int i=0;i<c+1;i++)
  44. 		vis[i]=0;
  45. 	while(1)
  46. 	{
  47.  
  48.  
  49. 				for(int j=0;j<v[s].size();j++)
  50. 				{
  51.                    if(vis[v[s][j]]==1)
  52.                    	continue;
  53.                    vis[v[s][j]]=1;
  54.                    q.push(v[s][j]);
  55. 				}
  56. 				int add=bfs(v,vis,c);
  57. 				if(add==0)
  58. 					break;
  59. 				v[add].push_back(s);
  60. 				ans++;
  61. 			  int flag=0;
  62. 		    for(int i=1;i<c+1;i++)
  63. 		    {
  64. 		    	if(vis[i]==0)
  65. 		    	{flag=1;
  66. 		    		for(int j=1;j<c+1;j++)
  67. 		    		{
  68. 		    			vis[j]=0;
  69. 		    		}
  70. 		    		i=c+2;
  71. 		    	}
  72. 		    }
  73. 		    if(flag==0)
  74. 		    	break;
  75.  
  76.  
  77.  
  78. 	}
  79. 	cout<<ans<<endl;
  80.  
  81. }
Success #stdin #stdout 0s 4308KB
comments (?)
stdin
copy 
9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1
stdout
copy 
0
https://ideone.com/BsJb4J
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!