fork(1) download
copy 
  1. #include <vector>
  2. #include <queue>
  3. #include <map>
  4. #include <set>
  5. #include <utility>
  6. #include <algorithm>
  7. #include <sstream>
  8. #include <iostream>
  9. #include <cstdio>
  10. #include <cmath>
  11. #include <cstring>
  12. #include<iomanip>
  13. using namespace std;
  14.  
  15. typedef long long ll;
  16. typedef vector <int> vi;
  17. typedef pair< int ,int > pii;
  18. #define pb push_back
  19. #define sz size()
  20. #define ln length()
  21. #define fore(i,a,b) for(int i=a;i<b;i++)
  22. #define fores(i,a,b) for(int i=a;i<=b;i++)
  23. #define ford(i,a,b) for(int i=a;i>=b;i--)
  24. #define all(a) a.begin(),a.end()
  25. #define mp make_pair
  26. #define ff first
  27. #define ss second
  28. #define MOD 1000000007
  29. vector<vi> adj;
  30. vi done;
  31. map<string,int> track;
  32. bool dfs(int i)
  33. {
  34. 	done[i] = 1;
  35. 	bool found = true;
  36. 	int nn = adj.sz;
  37. 	fore(j,0,adj[i].sz)
  38. 	{
  39. 		if(adj[i][j]+1<=nn)
  40. 		{
  41. 			if((done[adj[i][j]]==0))
  42. 				found = found && dfs(adj[i][j]);
  43. 			else if(done[adj[i][j]]==1)
  44. 				found = false;
  45. 		}
  46. 		else
  47. 			found = false;
  48. 	}
  49. 	if(found)
  50. 		done[i] = 2;
  51. 	else
  52. 		done[i] = 1;
  53. 	return found;
  54. }
  55. int main() {
  56. 	int tid = 0;
  57. 	string s ;
  58. 	getline(cin,s);
  59. 	while(!s.empty())
  60. 	{
  61. 		cout<<s<<endl;
  62. 		int n = s.ln;
  63. 		string temp2 = "";
  64. 		int i = 0;
  65. 		while(s[i]!=' ')
  66. 		{
  67. 			temp2+=s[i];
  68. 			i++;
  69. 		}
  70. 		if(track.count(temp2)>0)
  71. 		{
  72. 			if(track[temp2]+1>adj.sz)
  73. 				adj.resize(track[temp2]+1);
  74. 		}
  75. 		else
  76. 		{
  77. 			track.insert(pair<string, int>(temp2, tid));
  78. 			tid++;
  79. 			if(track[temp2]+1>adj.sz)
  80. 				adj.resize(track[temp2]+1);
  81. 		}
  82. 		int cur = track[temp2];
  83. 		i++;
  84. 		temp2 = "";
  85. 		for(;i<n;i++)
  86. 		{
  87. 			if(s[i]!=' ')
  88. 				temp2+=s[i];
  89. 			else
  90. 			{
  91. 				if(temp2 == "0")
  92. 					break;
  93. 				if(track.count(temp2)>0)
  94. 				{
  95. 					adj[cur].pb(track[temp2]);
  96. 				}
  97. 				else
  98. 				{
  99. 					track.insert(mp(temp2,tid));
  100. 					tid++;
  101. 					adj[cur].pb(track[temp2]);
  102. 				}
  103. 				temp2 = "";
  104. 			}
  105. 		}
  106. 		getline(cin,s);
  107. 	}
  108. 	int nn = adj.sz;
  109. 	done.resize(nn);
  110. 	fore(i,0,nn)
  111. 		done[i] = 0;
  112. 	fore(i,0,nn)
  113. 	{
  114. 		if(done[i]==0)
  115. 			dfs(i);
  116. 	}
  117. 	ll fa = 0;
  118. 	fore(i,0,nn)
  119. 	{
  120. 		if(done[i] == 2)
  121. 			fa++;
  122. 	}
  123. 	cout<<fa;
  124. 	return 0;
  125. }
  126.  
Runtime error #stdin #stdout 0.07s 3492KB
comments ()
stdin
copy 
a e 0
e 0
stdout
copy 
Standard output is empty
https://ideone.com/7QTl1m
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!