fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5. template<class T> inline void chkmax(T &x, const T &y) { if(x < y) x = y; }
  6. template<class T> inline void chkmin(T &x, const T &y) { if(x > y) x = y; }
  7. const int MAXN = (1 << 20);
  8.  
  9. int n, m, s, c;
  10. vector<pair<int, int> > adj[MAXN];
  11. pair<int, int> def_ord[MAXN];
  12.  
  13. void read()
  14. {
  15. 	cin >> n >> m >> s;
  16. 	c = 0;
  17.  
  18. 	for(int i = 0; i < m; i++)
  19. 	{
  20. 		int type, u, v;
  21. 		cin >> type >> u >> v;
  22. 		if(type == 2)
  23. 		{
  24. 			c++;
  25. 			adj[u].push_back({v, c});
  26. 			adj[v].push_back({u, c});
  27. 			def_ord[c] = {u, v};			
  28. 		}
  29. 		else adj[u].push_back({v, -1});
  30. 	}
  31. }
  32.  
  33. pair<int, int> ord[MAXN];
  34. int answer = 0;
  35. bool visited[MAXN];
  36.  
  37. void dfs(int u, bool mn)
  38. {
  39. 	answer++;
  40. 	visited[u] = 1;
  41. 	for(auto e: adj[u])
  42. 		if(!visited[e.first])
  43. 		{
  44. 			int v = e.first;
  45. 			if(e.second == -1) dfs(v, mn);
  46. 			else 
  47. 			{
  48. 				if(mn) ord[e.second] = {v, u};
  49. 				else
  50. 				{
  51. 					ord[e.second] = {u, v};
  52. 					dfs(v, mn);
  53. 				}
  54. 			}
  55. 		}
  56. }
  57.  
  58. void solve(bool mn)
  59. {
  60. 	answer = 0;
  61. 	memset(visited, 0, sizeof(visited));
  62. 	dfs(s, mn);
  63.  
  64. 	cout << answer << endl;
  65. 	for(int i = 1; i <= c; i++)
  66. 		if(ord[i] == def_ord[i]) cout << "+";
  67. 		else cout << "-";
  68. 	cout << endl;
  69. }
  70.  
  71. void solve()
  72. {
  73. 	solve(0);
  74. 	solve(1);
  75. }
  76.  
  77. int main()
  78. {
  79. 	ios_base::sync_with_stdio(false);
  80. 	cin.tie(NULL);
  81.  
  82. 	read();
  83. 	solve();
  84. 	return 0;
  85. }
  86.  
  87.  
Success #stdin #stdout 0s 57224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1

1
https://ideone.com/nOSD4D
language:
C++ (gcc 8.3)
created:
7 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!