fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. #define eb emplace_back
  5. #define pu push
  6. #define ins insert
  7. #define fi first
  8. #define se second
  9. #define all(a) a.begin(),a.end()
  10. #define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  11. #define fu(x,a,b) for (auto x=a;x<=b;x++)
  12. #define fd(x,a,b) for (auto x=a;x>=b;x--)
  13. #define int ll
  14.  
  15. using namespace std;
  16. #pragma GCC optimize("Ofast")
  17. #pragma GCC optimize("unroll-loops")
  18. //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  19.  
  20. typedef pair<int, int> ii;
  21. const int N = 2e5+5;
  22. const int mod = 1e9+7;
  23. const int inf = 1e18;
  24. using cd = complex<double>;
  25. const long double PI = acos(-1);
  26. int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 
  27.  
  28. int n,m, deg[N], vis[N], t = 1, cnt[N];
  29. vector<int> adj[N];
  30. bool vis2[N];
  31.  
  32. void dfs(int u) {
  33. 	vis[u] = t;
  34. 	cnt[u] = 1;
  35. 	for (auto v : adj[u]) 
  36. 	{
  37. 		if (!vis[v]) dfs(v), cnt[u] += cnt[v];
  38. 		else if (vis[v] != t) cnt[u] += cnt[v];
  39. 	}
  40. }
  41.  
  42. int count(int u) 
  43. {
  44. 	vis2[u] = 1;
  45.     int res = 1;
  46. 	for (auto v : adj[u]) 
  47. 	{
  48. 		if (!vis2[v]) res += count(v);
  49. 	}
  50.     return res;
  51. }
  52.  
  53. void solve()
  54. {
  55. 	t = 1;
  56. 	for (int i = 1; i <= n; i++) adj[i].clear(), cnt[i] = 0, vis[i] = 0, deg[i] = 0, vis2[i] = 0;
  57. 	for (int i = 0; i < m; i++) 
  58. 	{
  59. 		int u,v; cin>>u>>v;
  60. 		adj[u].pb(v);
  61. 		deg[v]++;
  62. 	}
  63. 	int mx = 0, pos;
  64. 	for (int i = 1; i <= n; i++) 
  65. 	{
  66. 		if (deg[i] == 0) 
  67. 		{
  68. 			dfs(i);
  69. 			// cout<<i<<" "<<cnt[i]<<endl;
  70. 			if (cnt[i] > mx) mx = cnt[i], pos = i;
  71. 			t++;
  72. 			// cout<<cnt[i]<<endl;
  73. 		}
  74. 	}
  75. 	int ans = count(pos);
  76. 	cout<<pos<<" "<<ans;
  77. }
  78.  
  79. signed main()
  80. {
  81. 	bruh
  82. 	// freopen("journey.in", "r", stdin);
  83.     // freopen("journey.out", "w", stdout);
  84. 	// cin>>t;
  85. 	while (cin>>n)
  86. 	{
  87. 		if (n == 0) break;
  88. 		cin>>m;
  89. 		solve();
  90. 		cout<<"\n";
  91. 	}
  92. }
Success #stdin #stdout 0.01s 10056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/K5ugHS
language:
C++ (gcc 8.3)
created:
11 days 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!